High-dimensional estimation with geometric constraints: Table 1.

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.