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

Barbara Kaltenbacher; Jonas Offtermatt

doi:10.3934/ipi.2011.5.391

Article Contents

2011, Volume 5, Issue 2: 391-406. Doi: 10.3934/ipi.2011.5.391

This issue Previous Article Filtered Kirchhoff migration of cross correlations of ambient noise signals Next Article A regularized k-means and multiphase scale segmentation

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

Barbara Kaltenbacher^1, and
Jonas Offtermatt^2,

1.
Institute of Mathematics, University of Klagenfurt, Universitätsstraße 65-67, A-9020 Klagenfurt
2.
Department of Mathematics, University of Stuttgart, Pfaﬀenwaldring 57 D-70569 Stuttgart

Received: November 1, 2009

Revised: March 1, 2011

Published online: May 1, 2011

Abstract / Introduction Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 65J22, 92C42; Secondary: 65J20.

Citation:

Related Papers

Cited by

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.