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. Google Scholar

[2]

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

[3]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[8]

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

[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. Google Scholar

[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. Google Scholar

[11]

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

[12]

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

[13]

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

[14]

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

[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. Google Scholar

[16]

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

[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. Google Scholar

[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). Google Scholar

[19]

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

[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. Google Scholar

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. Google Scholar

[2]

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

[3]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[8]

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

[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. Google Scholar

[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. Google Scholar

[11]

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

[12]

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

[13]

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

[14]

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

[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. Google Scholar

[16]

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

[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. Google Scholar

[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). Google Scholar

[19]

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

[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. Google Scholar

[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

2018 Impact Factor: 1.469

Metrics

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

Other articles
by authors

[Back to Top]