Geometrizing Local Rates of Convergence for High-Dimensional Linear Inverse Problems
作者： Alexander Rakhlin , T. Tony Cai , Tengyuan Liang
DOI:
关键词:
摘要: This paper presents a unified theoretical framework for the analysis of general ill-posed linear inverse model which includes as special cases noisy compressed sensing, sign vector recovery, trace regression, orthogonal matrix estimation, and completion. We propose computationally feasible convex program problem develop to characterize local rate convergence. The theory is built based on conic geometry duality. difficulty estimation captured by geometric characterization tangent cone through complexity measures -- Gaussian width covering entropy.
arxiv.org参考文章(46)
Y. Gordon, On Milman's inequality and random subspaces which escape through a mesh in ℝ n Springer, Berlin, Heidelberg. pp. 84- 106 ,(1988) , 10.1007/BFB0081737
A. A. Giannopoulos, V. D. Milman, M. Rudelson, Convex bodies with minimal mean width Springer, Berlin, Heidelberg. pp. 81- 93 ,(2000) , 10.1007/BFB0107209
Peter Bhlmann, Sara van de Geer, Statistics for High-Dimensional Data: Methods, Theory and Applications ,(2011)
David Pollard, Empirical Processes: Theory and Applications ,(1990)
Alexandre B. Tsybakov, Introduction to Nonparametric Estimation ,(2008)
Yuhong Yang, Andrew Barron, None, Information-theoretic determination of minimax rates of convergence Annals of Statistics. ,vol. 27, pp. 1564- 1599 ,(1999) , 10.1214/AOS/1017939142
Bin Yu, Assouad, Fano, and Le Cam Festschrift for Lucien Le Cam. pp. 423- 435 ,(1997) , 10.1007/978-1-4612-1880-7_29
Michel Ledoux, Michel Talagrand, Probability in Banach Spaces: Isoperimetry and Processes ,(1991)
Roman Vershynin, Estimation in High Dimensions: A Geometric Perspective Sampling Theory, a Renaissance. pp. 3- 66 ,(2015) , 10.1007/978-3-319-19749-4_1
Dennis Amelunxen, Martin Lotz, Michael B. McCoy, Joel A. Tropp, Living on the edge: A geometric theory of phase transitions in convex optimization 2013... ,(2013) , 10.21236/ADA591124