Source-linked AI summary
High-dimensional estimation with geometric constraints
Yaniv Plan, Roman Vershynin, Elena Yudovina
TL;DR
The paper addresses signal estimation when observations depend on inner products through an unknown, potentially nonlinear relationship and the signal has known structure. It combines linear estimation with projection onto a feasible set and shows that, under general conditions, this estimator is minimax optimal up to a constant, even with unknown non-invertible nonlinearities in high-noise settings.
Problem
Signal estimation is difficult when the relationship between measurements and observations is unknown or nonlinear, while exploiting known signal structure requires a general framework.
Method
The paper uses a two-step estimator that forms a linear estimate and metrically projects it onto a known feasible set K, with mean width measuring its effective dimension.
Results
Under mild assumptions in the high-noise regime, the estimator is minimax optimal up to a constant, and unknown non-invertible nonlinearities often cause only scaling-information loss and an extra numerical constant in the error bound.
Takeaways & Limitations
Unknown, non-invertible observation nonlinearities often do not significantly impair signal estimation when the signal structure is exploited.
Takeaways & Limitations
The method is inappropriate when the observation function is even and the associated signal-strength parameter μ equals zero; sharp non-asymptotic constants remain an open question.
Abstract
from arXiv · showhide
Consider measuring an n-dimensional vector x through the inner product with several measurement vectors, a_1, a_2, ..., a_m. It is common in both signal processing and statistics to assume the linear response model y_i = <a_i, x> + e_i, where e_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 paper we propose a general model where it is only assumed that each observation y_i may depend on a_i only through <a_i, x>. 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. 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 non-linearity in the observations does not significantly reduce one's ability to determine the signal, even when the non-linearity may be non-invertible. Our results may be specialized to understand the effect of non-linearities in compressed sensing.
1. Introduction
The paper studies signal recovery when observations depend on inner products through an unknown, possibly nonlinear function and the signal lies in a known structured set. It proposes linear estimation followed by projection onto that set, with performance governed by mean width.
- Motivation: The model allows observations to follow an unknown relationship with <a_i, x>, covering linear and generalized linear settings, including binary data.The observation link may be unknown and need not be invertible.
- Signal structure: Signal structure is encoded by a known feasible set K, encompassing examples such as sparsity, low-rank matrices, manifolds, and compressible images.The paper aims to quantify how using K improves estimation.
- Estimator: The proposed estimator first computes a linear estimate and then metrically projects it onto K.The linear estimate is unbiased for a scaled signal under the model, while projection incorporates the available structure.
- Geometric analysis: Mean width measures the effective size of K and describes the dimension-reduction benefit available from exploiting signal structure.The squared mean width of a properly scaled set can be viewed as an essential dimension that is robust to small perturbations.
- Main results: Under general conditions, the projection-based estimator is minimax optimal up to a constant and can substantially outperform linear estimation.The main theorem gives a non-asymptotic characterization of the benefit of using K.
2. Feasible sets K: consequences and examples
The paper compares feasible-set projection with linear estimation and specializes the resulting geometric guarantees to cones, sparse and dictionary-sparse vectors, and low-rank matrices. Across these examples, the required observations scale with the feasible set’s effective dimension, while projection can substantially improve accuracy.
- General sets: comparison with linear estimation: For the ℓ1-ball, the error rate can exhibit the unusual dependence O(m^-1/4), and local mean width can improve logarithmic factors.The paper states that this rate can be sharp and minimax optimal for many models when m is not too large.
- General sets: comparison with linear estimation: Projection onto a feasible set can only improve estimation accuracy, often substantially, relative to the linear estimator.For general star-shaped sets, the projected estimator has an upper bound no worse than linear estimation up to an absolute constant factor.
- General cones: m = O(w1(K)^2) observations suffice for accurate estimation when K is a cone.Here w1(K)^2 is interpreted as the cone’s essential dimension.
- The set of sparse vectors: For s-sparse vectors in R^n, m ∼ s log(2n/s) observations are sufficient, with hard thresholding providing an efficient projection.The sparse feasible set contains vectors with at most s nonzero entries, and projection retains the s largest coordinates.
- The set of low-rank matrices: For a rank-r matrix, m ∼ r(d1 + d2) observations suffice for estimating a d1 × d2 matrix, including the matrix-completion setting.The matrix-completion estimator is accurate under m ≥ d log d, and its noisy error is minimax optimal up to a constant when ν ≥ ζ.
- Sparse in a dictionary: For approximately sparse vectors in R^n, m ∼ s log n observations are sufficient, while dictionary-sparse signals admit the analogous rate m ∼ s log n.Dictionary sparsity covers signals sparse after a linear transformation, including images represented in wavelet bases.
3. Observations yi: consequences and examples
The paper specializes its general estimator to linear, noisy linear, nonlinear, and binary observations, showing how signal structure controls estimation error across these models.
- The linear-observation corollary gives an error guarantee for signals in a star-shaped feasible set, with a cone specialization.
- Noisy linear observations fit the single-index model, and the resulting error reflects both signal magnitude and noise level.
- When noise exceeds signal strength, projection onto the feasible set can still yield accurate estimates and is minimax optimal up to a constant under general conditions.
- Unknown nonlinear links may be discontinuous, non-invertible, or nonmonotonic, yet estimation does not require knowing the link function.
- The method’s quality depends on parameters tied to the link, and even functions with µ = 0 make this signal-estimation approach inappropriate.
- For binary observations, the framework covers logistic and related models, while 1-bit compressed sensing requires m ∼ s log(2n/s) observations for an s-sparse vector.
4. Optimality
The paper establishes when projection-based estimation is minimax-optimal up to constants for linear and unknown nonlinear observations. In high-noise settings, unknown noninvertible nonlinearities often preserve signal-estimation accuracy up to a constant factor.
- The analysis seeks conditions making the projection estimator minimax-optimal up to a numerical constant for structured feasible sets K.
- Unknown, noninvertible nonlinearities often do not significantly decrease signal-estimation ability when measurements are noisy.
- Linear model: When noise is at least as large as the signal norm, the linear upper and lower bounds match most closely.
- Linear model: For sparse vectors, low-rank matrices, and the ℓ1-ball, the geometric ratio α is bounded by numerical constants, yielding minimax error up to a constant factor.
- Nonlinear model: For nonlinear observations, the estimation error increases by at most a constant factor when the comparison condition between nonlinear and linear bounds holds.
- Nonlinear model: Uniform nonlinear error bounds apply to finite linear combinations of admissible functions, including odd nondecreasing polynomials of bounded degree.
5. Related results: Low M∗estimate, Chatterjee’s least squares estimate
This section connects the estimation problem to the low M∗ estimate and to Chatterjee’s least-squares framework. These connections explain geometric error control for consistent estimates and clarify the role of projection in related models.
- Low M∗ estimate: The low M∗ estimate bounds the diameter of sections of K parallel to the random nullspace of the measurement matrix.
- Low M∗ estimate: A feasible point in K consistent with the linear observations has high-probability error at most t under the low M∗ condition.
- Low M∗ estimate: For cones, the geometric condition can yield exact recovery as the scale t tends to zero.
- Low M∗ estimate: Exact recovery is impossible in the single-index model because of noise and the unknown nonlinear dependence of observations.
- Chatterjee’s least squares estimate: The current model uses an m × n Gaussian projection, whereas Chatterjee’s model observes all n coordinates through an identity measurement matrix.
- Chatterjee’s least squares estimate: Chatterjee’s least-squares estimator equals metric projection onto K, matching the second step of the paper’s estimator.
6. Connections to statistics and econometrics
The paper places its semiparametric single-index estimator among statistical and econometric methods while emphasizing its structural and nonlinear scope. It relates the approach to GLMs, sparse nonparametric models, and learning-theoretic estimators, while identifying remaining sharp-constant questions.
- Connections to statistics and econometrics: The method requires conditional independence of the noise and covariates given the single index.
- Connections to statistics and econometrics: The single-index framework includes linear, logistic, and Poisson regressions but does not contain or equal the full class of GLMs.
- Connections to statistics and econometrics: Unlike methods based on average derivatives, the paper allows nondifferentiable links such as the sign function.
- High-dimensional extensions: Moving from single-index recovery to sparse nonparametric modeling requires exponentially more measurements in the sparsity level, though not in the full parameter dimension.
- Statistical learning connections: The projection method can use milder structural conditions and often be more computationally efficient than optimization programs discussed in related work.
- Statistical learning connections: Sharp constants are known for generalized Lasso in linear models, but obtaining them non-asymptotically for the nonlinear model remains open.
7. Discussion
The discussion finds that projection-based estimation remains effective under unknown nonlinear observations, with performance characterized by mean width and supported mainly under Gaussian measurements.
- In high noise, the projection-based estimator is minimax optimal up to a constant under mild assumptions.The estimator combines linear estimation with projection onto the structure-encoding set.
- Unknown, noninvertible nonlinearities often reduce estimation only through lost scaling information and an extra numerical constant in the error bound.
- Mean width quantifies the gain from dimension reduction when projecting onto the signal-structure set.
- The results provide a simple test for estimability, allow discontinuous and unknown nonlinearities, and quantify benefits of low-dimensional structure.
- The upper-bound theory relies on standard normal measurement vectors, while lower bounds allow much more general, even deterministic, measurement models.
- For Gaussian measurements with covariance Σ, multiplying the linear estimator by Σ^-1 preserves unbiasedness when Σ is known or estimable and well-conditioned.
8. Proofs of Proposition 1.1 and Theorem 1.3
The proofs exploit Gaussian orthogonal decomposition to establish unbiasedness and independence, then control projection error through geometric properties of the feasible set.
- Gaussian orthogonal decomposition separates each measurement into the signal direction and its orthogonal complement, with independent components.
- Because observations depend on measurements only through the signal-direction inner product, each observation is independent of the orthogonal component.
- The linear estimator has expectation μx̄, so it estimates the normalized signal up to a scalar factor.
- Projection-error bounds reduce the analysis to distances and dual-norm control over localized difference sets derived from K.
- Gaussian concentration and convexity extend the geometric estimates from the orthogonal subspace to the full ambient space.
- Substituting the concentration estimates into the projection bound completes the proof of Theorem 1.3.
9. High-probability version of Theorem 1.3
The paper strengthens the expected-error result to a high-probability guarantee using sub-Gaussian observations and concentration inequalities, while separate arguments establish minimax lower bounds.
- The high-probability proof controls the linear-estimation and orthogonal-noise terms using Bernstein-type and Gaussian concentration inequalities.
- Sub-Gaussian observations are sufficient for the concentration argument, including responses generated by nonlinearities with at most linear growth.
- The nonlinear estimator achieves a high-probability error bound when the normalized signal scaled by μ lies in a fixed star-shaped set K.
- Fano’s inequality converts packing bounds for K into lower bounds on the expected error of every estimator.
- When K is very small, such as a one-dimensional subspace, a simpler two-point indistinguishability argument replaces the main Fano case.