Reconstruction and subgaussian operators in asymptotic geometric analysis

DOI10.1007/s00039-007-0618-7zbMath1163.46008MaRDI 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 processes; neighborly polytopes; approximate reconstruction; exact reconstruction; sub-Gaussian random vectors; asymptotic geometric analysis; linear measurements; \(\pm 1\) random polytopes; sub-Gaussian operators

Mathematics Subject Classification ID

52B05: Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)

46B07: Local theory of Banach spaces

46B09: Probabilistic methods in Banach space theory

94B75: Applications of the theory of convex sets and geometry of numbers (covering radius, etc.) to coding theory

52A22: Random convex sets and integral geometry (aspects of convex geometry)

62G99: Nonparametric inference

41A45: Approximation by arbitrary linear expressions

Related Items

Unnamed Item, High-dimensional estimation with geometric constraints: Table 1., Tensor-Structured Sketching for Constrained Least Squares, Extending the scope of the small-ball method, A Simple Tool for Bounding the Deviation of Random Matrices on Geometric Sets, On Multiplier Processes Under Weak Moment Assumptions, Upper bounds on product and multiplier empirical processes, On generic chaining and the smallest singular value of random matrices with heavy tails, Uniform estimates for order statistics and Orlicz functions, General nonexact oracle inequalities for classes with a subexponential envelope, 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, Discrepancy, chaining and subgaussian processes, Estimation of high-dimensional low-rank matrices, Empirical processes with a bounded \(\psi_1\) diameter, The Dantzig selector and sparsity oracle inequalities, A Bernstein-type inequality for suprema of random processes with applications to model selection in non-Gaussian regression, Sparse representations and approximation theory, 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, Iterative hard thresholding for compressed sensing, Sparsity in penalized empirical risk minimization, Aggregation via empirical risk minimization, Regularization in kernel learning, Analysis \(\ell_1\)-recovery with frames and Gaussian measurements, A subgaussian embedding theorem, 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, Improved bounds for sparse recovery from subsampled random convolutions, High-dimensional \(A\)-learning for optimal dynamic treatment regimes, On the optimality of the empirical risk minimization procedure for the convex aggregation problem, The springback penalty for robust signal recovery, Robust statistical learning with Lipschitz and convex loss functions, Robust covariance estimation under \(L_4\)-\(L_2\) norm equivalence, Randomized large distortion dimension reduction, On aggregation for heavy-tailed classes, Phase retrieval: stability and recovery guarantees, On the interval of fluctuation of the singular values of random matrices, Generalized notions of sparsity and restricted isometry property. II: Applications, \(\ell^1\)-analysis minimization and generalized (co-)sparsity: when does recovery succeed?, Learning without Concentration, Estimation in High Dimensions: A Geometric Perspective, Convex Recovery of a Structured Signal from Independent Random Linear Measurements, Suprema of Chaos Processes and the Restricted Isometry Property, Metric and classical fidelity uncertainty relations for random unitary matrices, Cosparsity in Compressed Sensing, Quantitative estimates of the convergence of the empirical covariance matrix in log-concave ensembles