High-dimensional estimation with geometric constraints

DOI10.1093/IMAIAI/IAW015zbMATH Open1383.62121arXiv1404.3749OpenAlexW2963403872MaRDI QIDQ4603716FDOQ4603716

Roman Vershynin, Y. Plan, Elena Yudovina

Publication date: 19 February 2018

Published in: Information and Inference: A Journal of the IMA (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1404.3749

Recommendations

• Geometric inference for general high-dimensional linear inverse problems
• Estimation in high dimensions: a geometric perspective
• On polyhedral estimation of signals via indirect observations
• The convex geometry of linear inverse problems
• Near-optimality of linear recovery from indirect observations

zbMATH Keywords

dimension reductionhigh-dimensional inferencematrix completioncompressed sensingmean widthsemiparametric single-index model

Mathematics Subject Classification ID

Nonparametric regression and quantile regression (62G08) Estimation in multivariate analysis (62H12) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Cites Work

• Statistics for high-dimensional data. Methods, theory and applications.
• A unified framework for high-dimensional analysis of \(M\)-estimators with decomposable regularizers
• Matrix estimation by universal singular value thresholding
• Consistent Estimation of Scaled Coefficients
• Title not available (Why is that?)
• Semiparametric Estimation of Index Coefficients
• 1-Bit matrix completion
• Regression analysis under link violation
• Exact matrix completion via convex optimization
• Minimax Rates of Estimation for High-Dimensional Linear Regression Over $\ell_q$-Balls
• Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements
• Direct estimation of the index coefficient in a single-index model
• The Generic Chaining
• 10.1162/153244303321897690
• A Probabilistic and RIPless Theory of Compressed Sensing
• Matrix Completion From a Few Entries
• One-bit compressed sensing by linear programming
• Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors
• Living on the edge: phase transitions in convex programs with random data
• Self-concordant analysis for logistic regression
• Title not available (Why is that?)
• How well can we estimate a sparse vector?
• A new perspective on least squares under convex constraint
• The Expected Norm of Random Matrices
• Reconstruction and subgaussian operators in asymptotic geometric analysis
• One-bit compressed sensing with non-Gaussian measurements
• Capturing ridge functions in high dimensions from point queries
• Mean width and diameter of proportional sections of a symmetric convex body
• Subspaces of Small Codimension of Finite-Dimensional Banach Spaces
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• How small can the intersection of a few rotations of a symmetric convex body be?
• Asymptotic formulas for the diameter of sections of symmetric convex bodies
• Sparse single-index model
• Robust 1-bit Compressed Sensing and Sparse Logistic Regression: A Convex Programming Approach
• Tight conditions for consistency of variable selection in the context of high dimensionality

Cited In (25)

• Geometric Representation of High Dimension, Low Sample Size Data
• Rigorous high-dimensional shadowing using containment: the general case
• Localized Gaussian width of \(M\)-convex hulls with applications to Lasso and convex aggregation
• Title not available (Why is that?)
• Estimation in High Dimensions: A Geometric Perspective
• Least squares estimation in the monotone single index model
• Estimating covariance and precision matrices along subspaces
• Just least squares: binary compressive sampling with low generative intrinsic dimension
• Solving equations of random convex functions via anchored regression
• Optimal estimation of slope vector in high-dimensional linear transformation models
• Concentration of measure bounds for matrix-variate data with missing values
• A unified approach to uniform signal recovery from nonlinear observations
• Understanding Implicit Regularization in Over-Parameterized Single Index Model
• Uniform recovery guarantees for quantized corrupted sensing using structured or generative priors
• A Simple Tool for Bounding the Deviation of Random Matrices on Geometric Sets
• Convergence guarantee for the sparse monotone single index model
• Misspecified nonconvex statistical optimization for sparse phase retrieval
• Generic error bounds for the generalized Lasso with sub-exponential data
• Preserving injectivity under subgaussian mappings and its application to compressed sensing
• Robust Decoding from 1-Bit Compressive Sampling with Ordinary and Regularized Least Squares
• The landscape of empirical risk for nonconvex losses
• Robust parameter estimation of regression models under weakened moment assumptions
• Sharp oracle inequalities for least squares estimators in shape restricted regression
• Optimal combination of linear and spectral estimators for generalized linear models
• Fast and Reliable Parameter Estimation from Nonlinear Observations

This page was built for publication: High-dimensional estimation with geometric constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4603716)