Reconstruction and subgaussian operators in asymptotic geometric analysis

DOI10.1007/S00039-007-0618-7zbMath1163.46008OpenAlexW2066086960MaRDI QIDQ2475582

Alain Pajor, Shahar Mendelson, Nicole Tomczak-Jaegermann

Publication date: 11 March 2008

Published in: Geometric and Functional Analysis. GAFA (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00039-007-0618-7

zbMATH Keywords

empirical processesneighborly polytopesapproximate reconstructionexact reconstructionsub-Gaussian random vectorsasymptotic geometric analysislinear measurements\(\pm 1\) random polytopessub-Gaussian operators

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Local theory of Banach spaces (46B07) Probabilistic methods in Banach space theory (46B09) Applications of the theory of convex sets and geometry of numbers (covering radius, etc.) to coding theory (94B75) Random convex sets and integral geometry (aspects of convex geometry) (52A22) Nonparametric inference (62G99) Approximation by arbitrary linear expressions (41A45)

Related Items (58)

A Simple Tool for Bounding the Deviation of Random Matrices on Geometric Sets ⋮ On Multiplier Processes Under Weak Moment Assumptions ⋮ On aggregation for heavy-tailed classes ⋮ On the interval of fluctuation of the singular values of random matrices ⋮ Sparsity in penalized empirical risk minimization ⋮ Improved bounds for sparse recovery from subsampled random convolutions ⋮ Aggregation via empirical risk minimization ⋮ Regularization in kernel learning ⋮ Cosparsity in Compressed Sensing ⋮ High-dimensional \(A\)-learning for optimal dynamic treatment regimes ⋮ Upper bounds on product and multiplier empirical processes ⋮ Suprema of Chaos Processes and the Restricted Isometry Property ⋮ Generalized notions of sparsity and restricted isometry property. II: Applications ⋮ The springback penalty for robust signal recovery ⋮ \(\ell^1\)-analysis minimization and generalized (co-)sparsity: when does recovery succeed? ⋮ Empirical processes with a bounded \(\psi_1\) diameter ⋮ Robust statistical learning with Lipschitz and convex loss functions ⋮ The Dantzig selector and sparsity oracle inequalities ⋮ Generic error bounds for the generalized Lasso with sub-exponential data ⋮ A unified approach to uniform signal recovery from nonlinear observations ⋮ Random sections of \(\ell_p\)-ellipsoids, optimal recovery and Gelfand numbers of diagonal operators ⋮ Sampling rates for \(\ell^1\)-synthesis ⋮ A Bernstein-type inequality for suprema of random processes with applications to model selection in non-Gaussian regression ⋮ Robust covariance estimation under \(L_4\)-\(L_2\) norm equivalence ⋮ On generic chaining and the smallest singular value of random matrices with heavy tails ⋮ Enhanced total variation minimization for stable image reconstruction ⋮ On the optimality of the empirical risk minimization procedure for the convex aggregation problem ⋮ Sparse representations and approximation theory ⋮ Analysis \(\ell_1\)-recovery with frames and Gaussian measurements ⋮ Uniform estimates for order statistics and Orlicz functions ⋮ High-dimensional estimation with geometric constraints: Table 1. ⋮ Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling ⋮ Explicit constructions of RIP matrices and related problems ⋮ Geometry of log-concave ensembles of random matrices and approximate reconstruction ⋮ Metric and classical fidelity uncertainty relations for random unitary matrices ⋮ General nonexact oracle inequalities for classes with a subexponential envelope ⋮ Phase retrieval: stability and recovery guarantees ⋮ Extending the scope of the small-ball method ⋮ A subgaussian embedding theorem ⋮ Toward a unified theory of sparse dimensionality reduction in Euclidean space ⋮ Dvoretzky type theorems for subgaussian coordinate projections ⋮ Decomposable norm minimization with proximal-gradient homotopy algorithm ⋮ Dimensionality reduction with subgaussian matrices: a unified theory ⋮ Randomized large distortion dimension reduction ⋮ Discrepancy, chaining and subgaussian processes ⋮ Quantitative estimates of the convergence of the empirical covariance matrix in log-concave ensembles ⋮ Estimation of high-dimensional low-rank matrices ⋮ Unnamed Item ⋮ Learning without Concentration ⋮ Estimation in High Dimensions: A Geometric Perspective ⋮ Convex Recovery of a Structured Signal from Independent Random Linear Measurements ⋮ Iterative hard thresholding for compressed sensing ⋮ Stability properties of neighbourly random polytopes ⋮ Sparse recovery in convex hulls via entropy penalization ⋮ A simple proof of the restricted isometry property for random matrices ⋮ Uniform uncertainty principle for Bernoulli and subgaussian ensembles ⋮ AdaBoost and robust one-bit compressed sensing ⋮ Tensor-Structured Sketching for Constrained Least Squares

This page was built for publication: Reconstruction and subgaussian operators in asymptotic geometric analysis