Geometric inference for general high-dimensional linear inverse problems. (English) Zbl 1357.62235
Summary: This paper presents a unified geometric framework for the statistical analysis of a general ill-posed linear inverse model which includes as special cases noisy compressed sensing, sign vector recovery, trace regression, orthogonal matrix estimation and noisy matrix completion. We propose computationally feasible convex programs for statistical inference including estimation, confidence intervals and hypothesis testing. A theoretical framework is developed to characterize the local estimation rate of convergence and to provide statistical inference guarantees. Our results are built based on the local conic geometry and duality. The difficulty of statistical inference is captured by the geometric characterization of the local tangent cone through the Gaussian width and Sudakov estimate.
Keywords:
linear inverse problems; high-dimensional statistics; statistical inference; convex relaxation; conic geometry; geometric functional analysisReferences:
| [1] | Amelunxen, D., Lotz, M., McCoy, M. B. and Tropp, J. A. (2013). Living on the edge: A geometric theory of phase transitions in convex optimization. Preprint. Available at . arXiv:1303.6672 · Zbl 1339.90251 |
| [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. (2013). Statistical significance in high-dimensional linear models. Bernoulli 19 1212-1242. · Zbl 1273.62173 · doi:10.3150/12-BEJSP11 |
| [4] | 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 |
| [5] | Cai, T., Liang, T. and Rakhlin, A. (2016). Supplement to “Geometric inference for general high-dimensional linear inverse problems.” . · Zbl 1357.62235 · doi:10.1214/15-AOS1426 |
| [6] | Cai, T., Liu, W. and Luo, X. (2011). A constrained \(\ell_{1}\) minimization approach to sparse precision matrix estimation. J. Amer. Statist. Assoc. 106 594-607. · Zbl 1232.62087 · doi:10.1198/jasa.2011.tm10155 |
| [7] | Cai, T. T. and Low, M. G. (2004). An adaptation theory for nonparametric confidence intervals. Ann. Statist. 32 1805-1840. · Zbl 1056.62060 · doi:10.1214/009053604000000049 |
| [8] | Cai, T. T. and Low, M. G. (2004). Minimax estimation of linear functionals over nonconvex parameter spaces. Ann. Statist. 32 552-576. · Zbl 1048.62054 · doi:10.1214/009053604000000094 |
| [9] | Cai, T. T. and Zhou, W. (2013). Matrix completion via max-norm constrained optimization. Preprint. Available at . arXiv:1303.0341 · Zbl 1342.62091 · doi:10.1214/16-EJS1147 |
| [10] | Candès, E. and Tao, T. (2007). The Dantzig selector: Statistical estimation when \(p\) is much larger than \(n\). Ann. Statist. 35 2313-2351. · Zbl 1139.62019 · doi:10.1214/009053606000001523 |
| [11] | Candès, E. J. and Davenport, M. A. (2013). How well can we estimate a sparse vector? Appl. Comput. Harmon. Anal. 34 317-323. · Zbl 1315.94019 · doi:10.1016/j.acha.2012.08.010 |
| [12] | Candès, E. J., Li, X., Ma, Y. and Wright, J. (2011). Robust principal component analysis? J. ACM 58 Art. 11, 37. · Zbl 1327.62369 · doi:10.1145/1970392.1970395 |
| [13] | Candes, E. J. and Plan, Y. (2010). Matrix completion with noise. Proceedings of the IEEE 98 925-936. |
| [14] | Candès, E. J. and Plan, Y. (2011). Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements. IEEE Trans. Inform. Theory 57 2342-2359. · Zbl 1366.90160 · doi:10.1109/TIT.2011.2111771 |
| [15] | Candès, E. J. and Recht, B. (2009). Exact matrix completion via convex optimization. Found. Comput. Math. 9 717-772. · Zbl 1219.90124 · doi:10.1007/s10208-009-9045-5 |
| [16] | Chandrasekaran, V., Recht, B., Parrilo, P. A. and Willsky, A. S. (2012). The convex geometry of linear inverse problems. Found. Comput. Math. 12 805-849. · Zbl 1280.52008 · doi:10.1007/s10208-012-9135-7 |
| [17] | Chatterjee, S. (2015). Matrix estimation by universal singular value thresholding. Ann. Statist. 43 177-214. · Zbl 1308.62038 · doi:10.1214/14-AOS1272 |
| [18] | Donoho, D. L. (1994). Statistical estimation and optimal recovery. Ann. Statist. 22 238-270. · Zbl 0805.62014 · doi:10.1214/aos/1176325367 |
| [19] | Dudley, R. M. (1967). The sizes of compact subsets of Hilbert space and continuity of Gaussian processes. J. Funct. Anal. 1 290-330. · Zbl 0188.20502 · doi:10.1016/0022-1236(67)90017-1 |
| [20] | Gordon, Y. (1988). On Milman’s inequality and random subspaces which escape through a mesh in \({\mathbb{R}}^{n}\). In Geometric Aspects of Functional Analysis (1986 / 87). Lecture Notes in Math. 1317 84-106. Springer, Berlin. · doi:10.1007/BFb0081737 |
| [21] | Gower, J. C. and Dijksterhuis, G. B. (2004). Procrustes Problems. Oxford Statistical Science Series 30 . Oxford Univ. Press, Oxford. · Zbl 1057.62044 |
| [22] | Jagabathula, S. and Shah, D. (2011). Inferring rankings using constrained sensing. IEEE Trans. Inform. Theory 57 7288-7306. · Zbl 1365.94060 · doi:10.1109/TIT.2011.2165827 |
| [23] | Javanmard, A. and Montanari, A. (2014). Confidence intervals and hypothesis testing for high-dimensional regression. J. Mach. Learn. Res. 15 2869-2909. · Zbl 1319.62145 |
| [24] | Johnstone, I. M. and Silverman, B. W. (1990). Speed of estimation in positron emission tomography and related inverse problems. Ann. Statist. 18 251-280. · Zbl 0699.62043 · doi:10.1214/aos/1176347500 |
| [25] | Khuri, S., Bäck, T. and Heitkötter, J. (1994). The zero/one multiple knapsack problem and genetic algorithms. In Proceedings of the 1994 ACM Symposium on Applied Computing 188-193. ACM, New York. |
| [26] | Koltchinskii, V. (2011). Von Neumann entropy penalization and low-rank matrix estimation. Ann. Statist. 39 2936-2973. · Zbl 1246.62138 · doi:10.1214/11-AOS926 |
| [27] | Koltchinskii, V., Lounici, K. and Tsybakov, A. B. (2011). Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion. Ann. Statist. 39 2302-2329. · Zbl 1231.62097 · doi:10.1214/11-AOS894 |
| [28] | Lecué, G. and Mendelson, S. (2013). Learning subgaussian classes: Upper and minimax bounds. Preprint. Available at . arXiv:1305.4825 |
| [29] | Ledoux, M. and Talagrand, M. (1991). Probability in Banach Spaces : Isoperimetry and Processes. Ergebnisse der Mathematik und Ihrer Grenzgebiete (3) 23 . Springer, Berlin. · Zbl 0748.60004 |
| [30] | Ma, Z. and Wu, Y. (2013). Volume ratio, sparsity, and minimaxity under unitarily invariant norms. Preprint. Available at . arXiv:1306.3609 · Zbl 1359.94135 · doi:10.1109/TIT.2015.2487541 |
| [31] | Mangasarian, O. L. and Recht, B. (2011). Probability of unique integer solution to a system of linear equations. European J. Oper. Res. 214 27-30. · Zbl 1218.90112 · doi:10.1016/j.ejor.2011.04.010 |
| [32] | Negahban, S. N., Ravikumar, P., Wainwright, M. J. and Yu, B. (2012). A unified framework for high-dimensional analysis of \(M\)-estimators with decomposable regularizers. Statist. Sci. 27 538-557. · Zbl 1331.62350 · doi:10.1214/12-STS400 |
| [33] | O’Sullivan, F. (1986). A statistical perspective on ill-posed inverse problems. Statist. Sci. 1 502-527. · Zbl 0625.62110 · doi:10.1214/ss/1177013525 |
| [34] | Oymak, S., Thrampoulidis, C. and Hassibi, B. (2013). Simple bounds for noisy linear inverse problems with exact side information. Preprint. Available at . arXiv:1312.0641 |
| [35] | Pisier, G. (1989). The Volume of Convex Bodies and Banach Space Geometry. Cambridge Tracts in Mathematics 94 . Cambridge Univ. Press, Cambridge. · Zbl 0698.46008 |
| [36] | Prokopyev, O. A., Huang, H. and Pardalos, P. M. (2005). On complexity of unconstrained hyperbolic 0-1 programming problems. Oper. Res. Lett. 33 312-318. · Zbl 1140.90469 · doi:10.1016/j.orl.2004.05.011 |
| [37] | Recht, B., Fazel, M. and Parrilo, P. A. (2010). Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev. 52 471-501. · Zbl 1198.90321 · doi:10.1137/070697835 |
| [38] | Rohde, A. and Tsybakov, A. B. (2011). Estimation of high-dimensional low-rank matrices. Ann. Statist. 39 887-930. · Zbl 1215.62056 · doi:10.1214/10-AOS860 |
| [39] | Talagrand, M. (1996). Majorizing measures: The generic chaining. Ann. Probab. 24 1049-1103. · Zbl 0867.60017 · doi:10.1214/aop/1065725175 |
| [40] | ten Berge, J. M. F. (1977). Orthogonal Procrustes rotation for two or more matrices. Psychometrika 42 267-276. · Zbl 0362.92020 · doi:10.1007/BF02294053 |
| [41] | Tibshirani, R. (1996). Regression shrinkage and selection via the lasso. J. R. Stat. Soc. Ser. B. Stat. Methodol. 58 267-288. · Zbl 0850.62538 |
| [42] | Tikhonov, A. and Arsenin, V. Y. (1977). Methods for Solving Ill-Posed Problems . Wiley, New York. · Zbl 0499.65030 |
| [43] | Valiant, L. G. and Vazirani, V. V. (1986). NP is as easy as detecting unique solutions. Theoret. Comput. Sci. 47 85-93. · Zbl 0621.68030 · doi:10.1016/0304-3975(86)90135-0 |
| [44] | van de Geer, S., Bühlmann, P., Ritov, Y. and Dezeure, R. (2014). On asymptotically optimal confidence regions and tests for high-dimensional models. Ann. Statist. 42 1166-1202. · Zbl 1305.62259 · doi:10.1214/14-AOS1221 |
| [45] | Vershynin, R. (2011). Lectures in geometric functional analysis. Available at . |
| [46] | Yang, Y. and Barron, A. (1999). Information-theoretic determination of minimax rates of convergence. Ann. Statist. 27 1564-1599. · Zbl 0978.62008 · doi:10.1214/aos/1017939142 |
| [47] | Ye, F. and Zhang, C. (2010). Rate minimaxity of the Lasso and Dantzig selector for the \(\ell_{q}\) loss in \(\ell_{r}\) balls. J. Mach. Learn. Res. 11 3519-3540. · Zbl 1242.62074 |
| [48] | Zhang, C. and Zhang, S. S. (2014). Confidence intervals for low dimensional parameters in high dimensional linear models. J. R. Stat. Soc. Ser. B. Stat. Methodol. 76 217-242. · doi:10.1111/rssb.12026 |
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.
