A regularized eigenmatrix method for unstructured sparse recovery

Koung Hee Leem; Jun Liu; George Pelekanos; Koung Hee Leem; Jun Liu; George Pelekanos

doi:10.3934/era.2024196

Electronic Research Archive

2024, Volume 32, Issue 7: 4365-4377. doi: 10.3934/era.2024196

Previous Article Next Article

Research article Special Issues

A regularized eigenmatrix method for unstructured sparse recovery

Department of Mathematics and Statistics, Southern Illinois University Edwardsville, Edwardsville, IL 62026, USA

Received: 23 April 2024 Revised: 24 June 2024 Accepted: 28 June 2024 Published: 11 July 2024

The recently developed data-driven eigenmatrix method shows very promising reconstruction accuracy in sparse recovery for a wide range of kernel functions and random sample locations. However, its current implementation can lead to numerical instability if the threshold tolerance is not appropriately chosen. To incorporate regularization techniques, we have proposed to regularize the eigenmatrix method by replacing the computation of an ill-conditioned pseudo-inverse by the solution of an ill-conditioned least squares system, which can be efficiently treated by Tikhonov regularization. Extensive numerical examples confirmed the improved effectiveness of our proposed method, especially when the noise levels were relatively high.
- eigenmatrix method,
- Tikhonov regularization,
- L-curve rule,
- ESPRIT algorithm
Citation: Koung Hee Leem, Jun Liu, George Pelekanos. A regularized eigenmatrix method for unstructured sparse recovery[J]. Electronic Research Archive, 2024, 32(7): 4365-4377. doi: 10.3934/era.2024196

Related Papers:

Abstract

The recently developed data-driven eigenmatrix method shows very promising reconstruction accuracy in sparse recovery for a wide range of kernel functions and random sample locations. However, its current implementation can lead to numerical instability if the threshold tolerance is not appropriately chosen. To incorporate regularization techniques, we have proposed to regularize the eigenmatrix method by replacing the computation of an ill-conditioned pseudo-inverse by the solution of an ill-conditioned least squares system, which can be efficiently treated by Tikhonov regularization. Extensive numerical examples confirmed the improved effectiveness of our proposed method, especially when the noise levels were relatively high.

References

[1]	M. Berljafa, S. Guttel, The RKFIT algorithm for nonlinear rational approximation, SIAM J. Sci. Comput., 39 (2017), A2049–A2071. https://doi.org/10.1137/15M1025426 doi: 10.1137/15M1025426
[2]	L. Ying, Analytic continuation from limited noisy Matsubara data, J. Comput. Phys., 469 (2022), 111549. https://doi.org/10.1016/j.jcp.2022.111549 doi: 10.1016/j.jcp.2022.111549
[3]	L. Ying, Pole recovery from noisy data on imaginary axis, J. Sci. Comput., 92 (2022), 107. https://doi.org/10.1007/s10915-022-01963-z doi: 10.1007/s10915-022-01963-z
[4]	D. Potts, M. Tasche, Parameter estimation for exponential sums by approximate Prony method, Signal Process., 90 (2010), 1631–1642. https://doi.org/10.1016/j.sigpro.2009.11.012 doi: 10.1016/j.sigpro.2009.11.012
[5]	D. Potts, M. Tasche, Parameter estimation for nonincreasing exponential sums by Prony-like methods, Linear Algebra Appl., 439 (2013), 1024–1039. https://doi.org/10.1016/j.laa.2012.10.036 doi: 10.1016/j.laa.2012.10.036
[6]	W. T. Weeks, Numerical inversion of Laplace transforms using Laguerre functions, J. ACM, 13 (1966), 419–429. https://doi.org/10.1145/321341.321351 doi: 10.1145/321341.321351
[7]	B. Davies, B. Martin, Numerical inversion of the Laplace transform: a survey and comparison of methods, J. Comput. Phys., 33 (1979), 1–32. https://doi.org/10.1016/0021-9991(79)90025-1 doi: 10.1016/0021-9991(79)90025-1
[8]	T. Peter, G. Plonka, A generalized Prony method for reconstruction of sparse sums of eigenfunctions of linear operators, Inverse Probl., 29 (2013), 025001. https://doi.org/10.1088/0266-5611/29/2/025001 doi: 10.1088/0266-5611/29/2/025001
[9]	A. Cohen, Numerical Methods for Laplace Transform Inversion, Springer New York, 2007.
[10]	S. Becker, J. Bobin, E. J. Candès, NESTA: a fast and accurate first-order method for sparse recovery, SIAM J. Imag. Sci., 4 (2011), 1–39. https://doi.org/10.1137/090756855 doi: 10.1137/090756855
[11]	E. C. Marques, N. Maciel, L. Naviner, H. Cai, J. Yang, A review of sparse recovery algorithms, IEEE Access, 7 (2018), 1300–1322. https://doi.org/10.1109/ACCESS.2018.2886471 doi: 10.1109/ACCESS.2018.2886471
[12]	L. Ying, Eigenmatrix for unstructured sparse recovery, Appl. Comput. Harmon. Anal., 71 (2024), 101653. https://doi.org/10.1016/j.acha.2024.101653 doi: 10.1016/j.acha.2024.101653
[13]	R. Roy, T. Kailath, ESPRIT-estimation of signal parameters via rotational invariance techniques, IEEE Trans. Acoust. Speech Signal Process., 37 (1989), 984–995. https://doi.org/10.1109/29.32276 doi: 10.1109/29.32276
[14]	H. Akaike, Information theory and an extension of the maximum likelihood principle, in Selected Papers of Hirotugu Akaike, Springer, (1998), 199–213. https://doi.org/10.1007/978-1-4612-1694-0_15
[15]	G. Schwarz, Estimating the dimension of a model, Ann. Stat., 6 (1978), 461–464. https://doi.org/10.1214/aos/1176344136 doi: 10.1214/aos/1176344136
[16]	R. Schmidt, Multiple emitter location and signal parameter estimation, IEEE Trans. Antennas Propag., 34 (1986), 276–280. https://doi.org/10.1109/TAP.1986.1143830 doi: 10.1109/TAP.1986.1143830
[17]	H. W. Engl, M. Hanke, A. Neubauer, Regularization of Inverse Problems, Springer Science & Business Media, 1996.
[18]	P. C. Hansen, Discrete inverse problems: insight and algorithms, SIAM, Philadelphia, 2010. https://doi.org/10.1137/1.9780898718836
[19]	A. Kirsch, An Introduction to the Mathematical Theory of Inverse Problems, Springer New York, 2011.
[20]	M. Benning, M. Burger, Modern regularization methods for inverse problems, Acta Numer., 27 (2018), 1–111. https://doi.org/10.1017/S0962492918000016 doi: 10.1017/S0962492918000016
[21]	K. Ito, B. Jin, Inverse problems: Tikhonov theory and algorithms, World Scientific, 2014.
[22]	H. W. Engl, Discrepancy principles for Tikhonov regularization of ill-posed problems leading to optimal convergence rates, J. Optim. Theory Appl., 52 (1987), 209–215. https://doi.org/10.1007/BF00941281 doi: 10.1007/BF00941281
[23]	F. S. V. Bazán, J. B. Francisco, An improved fixed-point algorithm for determining a Tikhonov regularization parameter, Inverse Probl., 25 (2009), 045007. https://doi.org/10.1088/0266-5611/25/4/045007 doi: 10.1088/0266-5611/25/4/045007
[24]	P. C. Hansen, Analysis of discrete ill-posed problems by means of the L-curve, SIAM Rev., 34 (1992), 561–580. https://doi.org/10.1137/1034115 doi: 10.1137/1034115
[25]	H. W. Engl, W. Grever, Using the L–curve for determining optimal regularization parameters, Numer. Math., 69 (1994), 25–31. https://doi.org/10.1007/s002110050078 doi: 10.1007/s002110050078
[26]	P. C. Hansen, J. S. Jørgensen, AIR Tools Ⅱ: algebraic iterative reconstruction methods, improved implementation, Numerical Algorithms, 79 (2018), 107–137. https://doi.org/10.1007/s11075-017-0430-x doi: 10.1007/s11075-017-0430-x
[27]	S. Gazzola, P. C. Hansen, J. G. Nagy, IR tools: a MATLAB package of iterative regularization methods and large-scale test problems, Numerical Algorithms, 81 (2019), 773–811. https://doi.org/10.1007/s11075-018-0570-7 doi: 10.1007/s11075-018-0570-7
[28]	U. Tautenhahn, On the asymptotical regularization of nonlinear ill-posed problems, Inverse Probl., 10 (1994), 1405–1418. https://doi.org/10.1088/0266-5611/10/6/014 doi: 10.1088/0266-5611/10/6/014
[29]	Y. Zhang, C. Chen, Stochastic asymptotical regularization for linear inverse problems, Inverse Probl., 39 (2023), 015007. https://doi.org/10.1088/1361-6420/aca70f doi: 10.1088/1361-6420/aca70f
[30]	A. Neubauer, On Nesterov acceleration for Landweber iteration of linear ill-posed problems, J. Inverse Ill-Posed Probl., 25 (2016), 381–390. https://doi.org/10.1515/jiip-2016-0060 doi: 10.1515/jiip-2016-0060
[31]	R. Gong, B. Hofmann, Y. Zhang, A new class of accelerated regularization methods, with application to bioluminescence tomography, Inverse Probl., 36 (2020), 055013. https://doi.org/10.1088/1361-6420/ab730b doi: 10.1088/1361-6420/ab730b
[32]	H. Robbins, S. Monro, A stochastic approximation method, Ann. Math. Stat., 22 (1951), 400–407. https://doi.org/10.1214/aoms/1177729586 doi: 10.1214/aoms/1177729586
[33]	H. Maurer, K. Holliger, D. E. Boerner, Stochastic regularization: smoothness or similarity? Geophys. Res. Lett., 25 (1998), 2889–2892. https://doi.org/10.1029/98GL02183
[34]	B. Jin, X. Lu, On the regularizing property of stochastic gradient descent, Inverse Probl., 35 (2019), 015004. https://doi.org/10.1088/1361-6420/aaea2a doi: 10.1088/1361-6420/aaea2a
[35]	H. G. Moura, E. C. Junior, A. Lenzi, V. C. Rispoli, On a stochastic regularization technique for ill-conditioned linear systems, Open Eng., 9 (2019), 52–60. https://doi.org/10.1515/eng-2019-0008 doi: 10.1515/eng-2019-0008
[36]	B. Jin, Z. Zhou, J. Zou, On the convergence of stochastic gradient descent for nonlinear ill-posed problems, SIAM J. Optim., 30 (2020), 1421–1450. https://doi.org/10.1137/19M1271798 doi: 10.1137/19M1271798
[37]	H. Choi, A. Thite, D. Thompson, A threshold for the use of Tikhonov regularization in inverse force determination, Appl. Acoust., 67 (2006), 700–719. https://doi.org/10.1016/j.apacoust.2005.11.003 doi: 10.1016/j.apacoust.2005.11.003
[38]	L. Ying, Multidimensional unstructured sparse recovery via eigenmatrix, preprint, arXiv: 2402.17215.
[39]	F. Andersson, M. Carlsson, ESPRIT for multidimensional general grids, SIAM J. Matrix Anal. Appl., 39 (2018), 1470–1488. https://doi.org/10.1137/17M1137267 doi: 10.1137/17M1137267

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)