High-dimensional estimation with geometric constraints: Table 1.
Authors:
- Y. PlanYPY. Plan
- R. VershyninRVR. Vershynin
- E. YudovinaEYE. Yudovina
Open Access
- 14 September 2016
- journal article
- research article
- Published by Oxford University Press (OUP) in Information and Inference: A Journal of the IMA
- Vol. 6 (1) , 1-40
Abstract
Consider measuring a vector $$x \in \mathbb{R}^n$$ through the inner product with several measurement vectors, $$a_1, a_2, \ldots, a_m$$. It is common in both signal processing and statistics to assume the linear response model $$y_i = \left\langle{a_i},{x}\right\rangle + \varepsilon_i$$, where $$\varepsilon_i$$ is a noise term. However, in practice the precise relationship between the signal $$x$$ and the observations $$y_i$$ may not follow the linear model, and in some cases it may not even be known. To address this challenge, in this article we propose a general model where it is only assumed that each observation$$y_i$$may depend on$$a_i$$only through$$\left\langle{a_i},{x}\right\rangle$$. We do not assume that the dependence is known. This is a form of the semiparametric-single index model, and it includes the linear model as well as many forms of the generalized linear model as special cases. We further assume that the signal $$x$$ has some structure, and we formulate this as a general assumption that $$x$$ belongs to some known (but arbitrary) feasible set $$K \subseteq \mathbb{R}^n$$. We carefully detail the benefit of using the signal structure to improve estimation. The theory is based on the mean width of $$K$$, a geometric parameter which can be used to understand its effective dimension in estimation problems. We determine a simple, efficient two-step procedure for estimating the signal based on this model—a linear estimation followed by metric projection onto $$K$$. We give general conditions under which the estimator is minimax optimal up to a constant. This leads to the intriguing conclusion that in the high noise regime, an unknown nonlinearity in the observations does not significantly reduce one’s ability to determine the signal, even when the nonlinearity may be non-invertible. Our results may be specialized to understand the effect of nonlinearities in compressed sensing.
Keywords
This publication has 39 references indexed in Scilit:
- One‐Bit Compressed Sensing by Linear ProgrammingCommunications on Pure and Applied Mathematics, 2013
- A Unified Framework for High-Dimensional Analysis of $M$-Estimators with Decomposable RegularizersStatistical Science, 2012
- Minimax Rates of Estimation for High-Dimensional Linear Regression Over $\ell_q$-BallsIEEE Transactions on Information Theory, 2011
- Nuclear-norm penalization and optimal rates for noisy low-rank matrix completionThe Annals of Statistics, 2011
- Exact Matrix Completion via Convex OptimizationFoundations of Computational Mathematics, 2009
- Asymptotic formulas for the diameter of sections of symmetric convex bodiesJournal of Functional Analysis, 2005
- Mean width and diameter of proportional sections of a symmetric convex bodyJournal für die reine und angewandte Mathematik (Crelles Journal), 1998
- Regression Analysis Under Link ViolationThe Annals of Statistics, 1989
- Subspaces of small codimension of finite-dimensional Banach spacesProceedings of the American Mathematical Society, 1986
- Random subspaces of proportional dimension of finite dimensional normed spaces: Approach through the isoperimetric inequality1985