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

[2]

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

[3]

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

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

[8]

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

[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.  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-1457. 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), 115017(24pp).  Google Scholar

[12]

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

[13]

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

[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. 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-2504. 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-442. 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-6168. 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-97. doi: 10.1103/RevModPhys.74.47.  Google Scholar

[2]

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

[3]

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

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

[8]

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

[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.  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-1457. 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), 115017(24pp).  Google Scholar

[12]

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

[13]

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

[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. 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-2504. 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-442. 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-6168. 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]

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

[3]

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

[4]

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

[5]

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

[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]

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

[8]

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

[9]

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

[10]

Avner Friedman. Free boundary problems arising in biology. Discrete & 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 & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021144

[12]

Monique Chyba, Benedetto Piccoli. Special issue on mathematical methods in systems biology. Networks & 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 & 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 & 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 & 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 & Imaging, , () : -. doi: 10.3934/ipi.2021051

[17]

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

[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 & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021168

[19]

M. Motta, C. Sartori. Exit time problems for nonlinear unbounded control systems. Discrete & 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 & Heterogeneous Media, 2007, 2 (2) : 359-381. doi: 10.3934/nhm.2007.2.359

2020 Impact Factor: 1.639

Metrics

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

Other articles
by authors

[Back to Top]