Solution of linear ill-posed problems using overcomplete dictionaries. (English) Zbl 1346.62061

Summary: In the present paper, we consider the application of overcomplete dictionaries to the solution of general ill-posed linear inverse problems. In the context of regression problems, there has been an enormous amount of effort to recover an unknown function using an overcomplete dictionary. One of the most popular methods, Lasso and its variants, is based on maximizing the likelihood, and relies on stringent assumptions on the dictionary, the so-called compatibility conditions, for a proof of its convergence rates. While these conditions may be satisfied for the original dictionary functions, they usually do not hold for their images due to contraction properties imposed by the linear operator.
In what follows, we bypass this difficulty by a novel approach, which is based on inverting each of the dictionary functions and matching the resulting expansion to the true function, thus, avoiding unrealistic assumptions on the dictionary and using Lasso in a predictive setting. We examine both the white noise and the observational model formulations, and also discuss how exact inverse images of the dictionary functions can be replaced by their approximate counterparts. Furthermore, we show how the suggested methodology can be extended to the problem of estimation of a mixing density in a continuous mixture. For all the situations listed above, we provide sharp oracle inequalities for the risk in a non-asymptotic setting.


62G05 Nonparametric estimation
62C10 Bayesian problems; characterization of Bayes procedures
Full Text: DOI arXiv Euclid


[1] Abramovich, F. and Silverman, B. W. (1998). Wavelet decomposition approaches to statistical inverse problems. Biometrika 85 115-129. · Zbl 0908.62095 · doi:10.1093/biomet/85.1.115
[2] Bickel, P. J., Ritov, Y. and Tsybakov, A. B. (2009). Simultaneous analysis of lasso and Dantzig selector. Ann. Statist. 37 1705-1732. · Zbl 1173.62022 · doi:10.1214/08-AOS620
[3] Bühlmann, P. and van de Geer, S. (2011). Statistics for High-Dimensional Data : Methods , Theory and Applications . Springer, Heidelberg. · Zbl 1273.62015 · doi:10.1007/978-3-642-20192-9
[4] Bunea, F., Tsybakov, A. and Wegkamp, M. (2007). Sparsity oracle inequalities for the Lasso. Electron. J. Stat. 1 169-194. · Zbl 1146.62028 · doi:10.1214/07-EJS008
[5] Bunea, F., Tsybakov, A. B., Wegkamp, M. H. and Barbu, A. (2010). Spades and mixture models. Ann. Statist. 38 2525-2558. · Zbl 1198.62025 · doi:10.1214/09-AOS790
[6] Candès, E. J. (2003). Ridgelets: Estimating with ridge functions. Ann. Statist. 31 1561-1599. · Zbl 1046.62037 · doi:10.1214/aos/1065705119
[7] Cavalier, L. and Golubev, Yu. (2006). Risk hull method and regularization by projections of ill-posed inverse problems. Ann. Statist. 34 1653-1677. · Zbl 1246.62082 · doi:10.1214/009053606000000542
[8] Cavalier, L. and Reiß, M. (2014). Sparse model selection under heterogeneous noise: Exact penalisation and data-driven thresholding. Electron. J. Stat. 8 432-455. · Zbl 1294.62058 · doi:10.1214/14-EJS889
[9] Cavalier, L., Golubev, G. K., Picard, D. and Tsybakov, A. B. (2002). Oracle inequalities for inverse problems. Ann. Statist. 30 843-874. Dedicated to the memory of Lucien Le Cam. · Zbl 1029.62032 · doi:10.1214/aos/1028674843
[10] Cohen, A., Hoffmann, M. and Reiß, M. (2004). Adaptive wavelet Galerkin methods for linear inverse problems. SIAM J. Numer. Anal. 42 1479-1501 (electronic). · Zbl 1077.65054 · doi:10.1137/S0036142902411793
[11] Comte, F. and Genon-Catalot, V. (2015). Adaptive Laguerre density estimation for mixed Poisson models. Electron. J. Stat. 9 1113-1149. · Zbl 1328.62228 · doi:10.1214/15-EJS1028
[12] Dalalyan, A. S., Hebiri, M. and Lederer, J. (2014). On the prediction performance of the Lasso. Preprint. Available at . arXiv:1402.1700 · Zbl 1359.62295 · doi:10.3150/15-BEJ756
[13] Dalalyan, A. S. and Salmon, J. (2012). Sharp oracle inequalities for aggregation of affine estimators. Ann. Statist. 40 2327-2355. · Zbl 1257.62038 · doi:10.1214/12-AOS1038
[14] Donoho, D. L. (1995). Nonlinear solution of linear inverse problems by wavelet-vaguelette decomposition. Appl. Comput. Harmon. Anal. 2 101-126. · Zbl 0826.65117 · doi:10.1006/acha.1995.1008
[15] Efromovich, S. and Koltchinskii, V. (2001). On inverse problems with unknown operators. IEEE Trans. Inform. Theory 47 2876-2894. · Zbl 1017.94508 · doi:10.1109/18.959267
[16] Golubev, Y. (2010). On universal oracle inequalities related to high-dimensional linear models. Ann. Statist. 38 2751-2780. · Zbl 1200.62074 · doi:10.1214/10-AOS803
[17] Goutis, C. (1997). Nonparametric estimation of a mixing density via the kernel method. J. Amer. Statist. Assoc. 92 1445-1450. · Zbl 0912.62055 · doi:10.2307/2965414
[18] Gupta, A. K. and Nagar, D. K. (2000). Matrix Variate Distributions . Chapman & Hall/CRC, Boca Raton, FL. · Zbl 0935.62064
[19] Hengartner, N. W. (1997). Adaptive demixing in Poisson mixture models. Ann. Statist. 25 917-928. · Zbl 0876.62042 · doi:10.1214/aos/1069362730
[20] Hoffmann, M. and Reiss, M. (2008). Nonlinear estimation for linear inverse problems with error in the operator. Ann. Statist. 36 310-336. · Zbl 1134.65038 · doi:10.1214/009053607000000721
[21] Kalifa, J. and Mallat, S. (2003). Thresholding estimators for linear inverse problems and deconvolutions. Ann. Statist. 31 58-109. · Zbl 1102.62318 · doi:10.1214/aos/1046294458
[22] Le Pennec, E. and Mallat, S. (2005). Sparse geometric image representations with bandelets. IEEE Trans. Image Process. 14 423-438. · doi:10.1109/TIP.2005.843753
[23] Liu, L., Levine, M. and Zhu, Y. (2009). A functional EM algorithm for mixing density estimation via nonparametric penalized likelihood maximization. J. Comput. Graph. Statist. 18 481-504. · doi:10.1198/jcgs.2009.07111
[24] Lounici, K., Pontil, M., van de Geer, S. and Tsybakov, A. B. (2011). Oracle inequalities and optimal inference under group sparsity. Ann. Statist. 39 2164-2204. · Zbl 1306.62156 · doi:10.1214/11-AOS896
[25] Meister, A. (2009). Deconvolution Problems in Nonparametric Statistics. Lecture Notes in Statistics 193 . Springer, Berlin. · Zbl 1178.62028 · doi:10.1007/978-3-540-87557-4
[26] Vershynin, R. (2012). Introduction to the non-asymptotic analysis of random matrices. In Compressed Sensing 210-268. Cambridge Univ. Press, Cambridge. · doi:10.1017/CBO9780511794308.006
[27] Walter, G. G. (1981). Orthogonal series estimators of the prior distribution. Sankhyā Ser. A 43 228-245. · Zbl 0528.62025
[28] Yuan, M. and Lin, Y. (2006). Model selection and estimation in regression with grouped variables. J. R. Stat. Soc. Ser. B Stat. Methodol. 68 49-67. · Zbl 1141.62030 · doi:10.1111/j.1467-9868.2005.00532.x
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.