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 and 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-97. doi: 10.1103/RevModPhys.74.47.

[2]

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

[3]

W. Bangerth, "Adaptive Finite Element Methods for the Identification of Distributed Parameters in Partial Differential Equations," PhD thesis, University of Heidelberg, Germany, 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-113. 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-794. 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-584.

[7]

M. Burger and A. Hofinger, Regularized greedy algorithms for network training with data noise, Computing, 74 (2005), 1-22. 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-985.

[9]

G. Chavent and R. Bissell, Indicator for the refinement of parametrization, In "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-1457. 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), 115017(24pp).

[12]

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

[13]

C. Geiger and C. Kanzow, "Numerische Verfahren zur Lösung Unrestringierter Optimierungsaufgaben," Springer, Berlin Heidelberg New York, 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-207.

[16]

Ralf Peeters and Ronald Westra, On the identification of sparse gene regulatory networks, In "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-2504. 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-442. 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-6168. 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-97. doi: 10.1103/RevModPhys.74.47.

[2]

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

[3]

W. Bangerth, "Adaptive Finite Element Methods for the Identification of Distributed Parameters in Partial Differential Equations," PhD thesis, University of Heidelberg, Germany, 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-113. 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-794. 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-584.

[7]

M. Burger and A. Hofinger, Regularized greedy algorithms for network training with data noise, Computing, 74 (2005), 1-22. 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-985.

[9]

G. Chavent and R. Bissell, Indicator for the refinement of parametrization, In "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-1457. 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), 115017(24pp).

[12]

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

[13]

C. Geiger and C. Kanzow, "Numerische Verfahren zur Lösung Unrestringierter Optimierungsaufgaben," Springer, Berlin Heidelberg New York, 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-207.

[16]

Ralf Peeters and Ronald Westra, On the identification of sparse gene regulatory networks, In "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-2504. 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-442. 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-6168. 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 and Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017

[2]

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

[3]

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

[4]

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

[5]

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

[6]

Gunther Uhlmann, Jian Zhai. Inverse problems for nonlinear hyperbolic equations. Discrete and Continuous Dynamical Systems, 2021, 41 (1) : 455-469. doi: 10.3934/dcds.2020380

[7]

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

[8]

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

[9]

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

[10]

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

[11]

Jin-Zi Yang, Yuan-Xin Li, Ming Wei. Fuzzy adaptive asymptotic tracking of fractional order nonlinear systems with uncertain disturbances. Discrete and Continuous Dynamical Systems - S, 2022, 15 (7) : 1615-1631. doi: 10.3934/dcdss.2021144

[12]

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

[13]

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

[14]

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

[15]

Abhishake Rastogi. Tikhonov regularization with oversmoothing penalty for nonlinear statistical inverse problems. Communications on Pure and Applied Analysis, 2020, 19 (8) : 4111-4126. doi: 10.3934/cpaa.2020183

[16]

Ru-Yu Lai, Laurel Ohm. Inverse problems for the fractional Laplace equation with lower order nonlinear perturbations. Inverse Problems and Imaging, 2022, 16 (2) : 305-323. doi: 10.3934/ipi.2021051

[17]

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

[18]

Ruitong Wu, Yongming Li, Jun Hu, Wei Liu, Shaocheng Tong. Switching mechanism-based event-triggered fuzzy adaptive control with prescribed performance for MIMO nonlinear systems. Discrete and Continuous Dynamical Systems - S, 2022, 15 (7) : 1713-1731. doi: 10.3934/dcdss.2021168

[19]

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

[20]

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

2021 Impact Factor: 1.483

Metrics

  • PDF downloads (91)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]