May  2011, 5(2): 391-406. doi: 10.3934/ipi.2011.5.391

A refinement and coarsening indicator algorithm for finding sparse solutions of inverse problems

1. 

Institute of Mathematics, University of Klagenfurt, Universitätsstraße 65-67, A-9020 Klagenfurt, Austria

2. 

Department of Mathematics, University of Stuttgart, Pfaffenwaldring 57 D-70569 Stuttgart, Germany

Received  November 2009 Revised  March 2011 Published  May 2011

In this paper we extend the idea of adaptive discretization by using refinement and coarsening indicators from papers by Chavent, Bissell, Benameur and Jaffré (cf., e.g., [5], [9]) to a general setting. This allows to make use of the relation between adaptive discretization and sparse paramerization in order to construct an algorithm for finding sparse solutions of inverse problems. We provide some first steps in the analysis of the proposed method and apply it to an inverse problem in systems biology, namely the reconstruction of gene networks in an ordinary differential equation (ODE) model. Here due to the fact that not all genes interact with each other, reconstruction of a sparse connectivity matrix is a key issue.
Citation: Barbara Kaltenbacher, Jonas Offtermatt. A refinement and coarsening indicator algorithm for finding sparse solutions of inverse problems. Inverse Problems & Imaging, 2011, 5 (2) : 391-406. doi: 10.3934/ipi.2011.5.391
References:
[1]

Réka Albert and Albert L. Barabási, Statistical mechanics of complex networks,, Reviews of Modern Physics, 74 (2002), 47. doi: 10.1103/RevModPhys.74.47.

[2]

Uri Alon, "An Introduction to Systems Biology: Design Principles of Biological Circuits,", Chapman & Hall/CRC, (2006).

[3]

W. Bangerth, "Adaptive Finite Element Methods for the Identification of Distributed Parameters in Partial Differential Equations,", PhD thesis, (2002).

[4]

Albert-László L. Barabási and Zoltán N. Oltvai, Network biology: understanding the cell's functional organization,, Nature reviews. Genetics, 5 (2004), 101. doi: 10.1038/nrg1272.

[5]

H. Ben Ameur, G. Chavent and J. Jaffré, Refinement and coarsening indicators for adaptive parametrization: Application to the estimation of hydraulic transmissivities,, Inverse Problems, 18 (2002), 775. doi: 10.1088/0266-5611/18/3/317.

[6]

H. Ben Ameur and B. Kaltenbacher, Regularization of parameter estimation by adaptive discretization using refinement and coarsening indicators,, J. Inv. Ill-Posed Probl., 10 (2003), 561.

[7]

M. Burger and A. Hofinger, Regularized greedy algorithms for network training with data noise,, Computing, 74 (2005), 1. doi: 10.1007/s00607-004-0081-3.

[8]

E. Candès and J. Romberg, Sparsity and incoherence in compressive sampling,, Inverse Problems, 23 (2006), 969.

[9]

G. Chavent and R. Bissell, Indicator for the refinement of parametrization,, "Proceedings of the International Symposium in Inverse Problems in Engineering Mechanics, Nagano, Japan,", (1998). doi: 10.1016/B978-008043319-6/50036-4.

[10]

I. Daubechies, M. Defrise and C. De Mol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint,, Communications on Pure and Applied Mathematics, 57 (2004), 1413. doi: 10.1002/cpa.20042.

[11]

L. Denis, D. Lorenz and D. Trede, Greedy solution of ill-posed problems: Error bounds and exact inversion,, Inverse Problems, 25 (2009).

[12]

H. W. Engl, M. Hanke and A. Neubauer, "Regularization of Inverse Problems,", Kluwer, (1996).

[13]

C. Geiger and C. Kanzow, "Numerische Verfahren zur Lösung Unrestringierter Optimierungsaufgaben,", Springer, (1999).

[14]

R. Griesse and D. A. Lorenz, A semismooth newton method for tikhonov functionals with sparsity constraints,, Inverse Problems, 24 (2008).

[15]

C. W. Groetsch and A. Neubauer, Convergence of a general projection method for an operator equation of the first kind,, Houston J. Mathem., (1988), 201.

[16]

Ralf Peeters and Ronald Westra, On the identification of sparse gene regulatory networks,, Proc 16th Intern Symp on Mathematical Theory of Networks,, (2004).

[17]

Paul Shannon, Andrew Markiel, Owen Ozier, Nitin S. Baliga, Jonathan T. Wang, Daniel Ramage, Nada Amin, Benno Schwikowski and Trey Ideker, Cytoscape: A software environment for integrated models of biomolecular interaction networks,, Genome research, 13 (2003), 2498. doi: 10.1101/gr.1239303.

[18]

Florian Steinke, Matthias Seeger and Koji Tsuda, Experimental design for efficient identification of gene regulatory networks using sparse bayesian models,, BMC Systems Biology, 1 (2007).

[19]

D. J. Watts and S. H. Strogatz, Collective dynamics of 'small-world' networks,, Nature, 393 (1998), 440. doi: 10.1038/30918.

[20]

M. K. Stephen Yeung, Jesper Tegnér and James J. Collins, Reverse engineering gene networks using singular value decomposition and robust regression,, Proceedings of the National Academy of Sciences of the United States of America, 99 (2002), 6163. doi: 10.1073/pnas.092576199.

show all references

References:
[1]

Réka Albert and Albert L. Barabási, Statistical mechanics of complex networks,, Reviews of Modern Physics, 74 (2002), 47. doi: 10.1103/RevModPhys.74.47.

[2]

Uri Alon, "An Introduction to Systems Biology: Design Principles of Biological Circuits,", Chapman & Hall/CRC, (2006).

[3]

W. Bangerth, "Adaptive Finite Element Methods for the Identification of Distributed Parameters in Partial Differential Equations,", PhD thesis, (2002).

[4]

Albert-László L. Barabási and Zoltán N. Oltvai, Network biology: understanding the cell's functional organization,, Nature reviews. Genetics, 5 (2004), 101. doi: 10.1038/nrg1272.

[5]

H. Ben Ameur, G. Chavent and J. Jaffré, Refinement and coarsening indicators for adaptive parametrization: Application to the estimation of hydraulic transmissivities,, Inverse Problems, 18 (2002), 775. doi: 10.1088/0266-5611/18/3/317.

[6]

H. Ben Ameur and B. Kaltenbacher, Regularization of parameter estimation by adaptive discretization using refinement and coarsening indicators,, J. Inv. Ill-Posed Probl., 10 (2003), 561.

[7]

M. Burger and A. Hofinger, Regularized greedy algorithms for network training with data noise,, Computing, 74 (2005), 1. doi: 10.1007/s00607-004-0081-3.

[8]

E. Candès and J. Romberg, Sparsity and incoherence in compressive sampling,, Inverse Problems, 23 (2006), 969.

[9]

G. Chavent and R. Bissell, Indicator for the refinement of parametrization,, "Proceedings of the International Symposium in Inverse Problems in Engineering Mechanics, Nagano, Japan,", (1998). doi: 10.1016/B978-008043319-6/50036-4.

[10]

I. Daubechies, M. Defrise and C. De Mol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint,, Communications on Pure and Applied Mathematics, 57 (2004), 1413. doi: 10.1002/cpa.20042.

[11]

L. Denis, D. Lorenz and D. Trede, Greedy solution of ill-posed problems: Error bounds and exact inversion,, Inverse Problems, 25 (2009).

[12]

H. W. Engl, M. Hanke and A. Neubauer, "Regularization of Inverse Problems,", Kluwer, (1996).

[13]

C. Geiger and C. Kanzow, "Numerische Verfahren zur Lösung Unrestringierter Optimierungsaufgaben,", Springer, (1999).

[14]

R. Griesse and D. A. Lorenz, A semismooth newton method for tikhonov functionals with sparsity constraints,, Inverse Problems, 24 (2008).

[15]

C. W. Groetsch and A. Neubauer, Convergence of a general projection method for an operator equation of the first kind,, Houston J. Mathem., (1988), 201.

[16]

Ralf Peeters and Ronald Westra, On the identification of sparse gene regulatory networks,, Proc 16th Intern Symp on Mathematical Theory of Networks,, (2004).

[17]

Paul Shannon, Andrew Markiel, Owen Ozier, Nitin S. Baliga, Jonathan T. Wang, Daniel Ramage, Nada Amin, Benno Schwikowski and Trey Ideker, Cytoscape: A software environment for integrated models of biomolecular interaction networks,, Genome research, 13 (2003), 2498. doi: 10.1101/gr.1239303.

[18]

Florian Steinke, Matthias Seeger and Koji Tsuda, Experimental design for efficient identification of gene regulatory networks using sparse bayesian models,, BMC Systems Biology, 1 (2007).

[19]

D. J. Watts and S. H. Strogatz, Collective dynamics of 'small-world' networks,, Nature, 393 (1998), 440. doi: 10.1038/30918.

[20]

M. K. Stephen Yeung, Jesper Tegnér and James J. Collins, Reverse engineering gene networks using singular value decomposition and robust regression,, Proceedings of the National Academy of Sciences of the United States of America, 99 (2002), 6163. doi: 10.1073/pnas.092576199.

[1]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017

[2]

Tayel Dabbous. Adaptive control of nonlinear systems using fuzzy systems. Journal of Industrial & Management Optimization, 2010, 6 (4) : 861-880. doi: 10.3934/jimo.2010.6.861

[3]

Xiao-Li Hu, Han-Fu Chen. Optimal Adaptive Regulation for Nonlinear Systems with Observation Noise. Journal of Industrial & Management Optimization, 2007, 3 (1) : 155-164. doi: 10.3934/jimo.2007.3.155

[4]

Judith R. Miller, Huihui Zeng. Stability of traveling waves for systems of nonlinear integral recursions in spatial population biology. Discrete & Continuous Dynamical Systems - B, 2011, 16 (3) : 895-925. doi: 10.3934/dcdsb.2011.16.895

[5]

Mapundi K. Banda, Michael Herty. Numerical discretization of stabilization problems with boundary controls for systems of hyperbolic conservation laws. Mathematical Control & Related Fields, 2013, 3 (2) : 121-142. doi: 10.3934/mcrf.2013.3.121

[6]

Eugene Kashdan, Dominique Duncan, Andrew Parnell, Heinz Schättler. Mathematical methods in systems biology. Mathematical Biosciences & Engineering, 2016, 13 (6) : i-ii. doi: 10.3934/mbe.201606i

[7]

Tan Bui-Thanh, Quoc P. Nguyen. FEM-based discretization-invariant MCMC methods for PDE-constrained Bayesian inverse problems. Inverse Problems & Imaging, 2016, 10 (4) : 943-975. doi: 10.3934/ipi.2016028

[8]

Avner Friedman. PDE problems arising in mathematical biology. Networks & Heterogeneous Media, 2012, 7 (4) : 691-703. doi: 10.3934/nhm.2012.7.691

[9]

Avner Friedman. Free boundary problems arising in biology. Discrete & Continuous Dynamical Systems - B, 2018, 23 (1) : 193-202. doi: 10.3934/dcdsb.2018013

[10]

Marin Kobilarov, Jerrold E. Marsden, Gaurav S. Sukhatme. Geometric discretization of nonholonomic systems with symmetries. Discrete & Continuous Dynamical Systems - S, 2010, 3 (1) : 61-84. doi: 10.3934/dcdss.2010.3.61

[11]

Michal Fečkan, Michal Pospíšil. Discretization of dynamical systems with first integrals. Discrete & Continuous Dynamical Systems - A, 2013, 33 (8) : 3543-3554. doi: 10.3934/dcds.2013.33.3543

[12]

Monique Chyba, Benedetto Piccoli. Special issue on mathematical methods in systems biology. Networks & Heterogeneous Media, 2019, 14 (1) : ⅰ-ⅱ. doi: 10.3934/nhm.20191i

[13]

Davide Guidetti. Some inverse problems of identification for integrodifferential parabolic systems with a boundary memory term. Discrete & Continuous Dynamical Systems - S, 2015, 8 (4) : 749-756. doi: 10.3934/dcdss.2015.8.749

[14]

M. Motta, C. Sartori. Exit time problems for nonlinear unbounded control systems. Discrete & Continuous Dynamical Systems - A, 1999, 5 (1) : 137-156. doi: 10.3934/dcds.1999.5.137

[15]

F. R. Guarguaglini, R. Natalini. Nonlinear transmission problems for quasilinear diffusion systems. Networks & Heterogeneous Media, 2007, 2 (2) : 359-381. doi: 10.3934/nhm.2007.2.359

[16]

Benjamin Couéraud, François Gay-Balmaz. Variational discretization of thermodynamical simple systems on Lie groups. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 1-28. doi: 10.3934/dcdss.2020064

[17]

N. Bellomo, A. Bellouquid. From a class of kinetic models to the macroscopic equations for multicellular systems in biology. Discrete & Continuous Dynamical Systems - B, 2004, 4 (1) : 59-80. doi: 10.3934/dcdsb.2004.4.59

[18]

Samuel Bowong, Jean Luc Dimi. Adaptive synchronization of a class of uncertain chaotic systems. Discrete & Continuous Dynamical Systems - B, 2008, 9 (2) : 235-248. doi: 10.3934/dcdsb.2008.9.235

[19]

Colin Guillarmou, Antônio Sá Barreto. Inverse problems for Einstein manifolds. Inverse Problems & Imaging, 2009, 3 (1) : 1-15. doi: 10.3934/ipi.2009.3.1

[20]

Sergei Avdonin, Pavel Kurasov. Inverse problems for quantum trees. Inverse Problems & Imaging, 2008, 2 (1) : 1-21. doi: 10.3934/ipi.2008.2.1

2017 Impact Factor: 1.465

Metrics

  • PDF downloads (11)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]