Reconstruction and subgaussian processes

DOI10.1016/J.CRMA.2005.04.032zbMATH Open1081.46013arXivmath/0506239OpenAlexW1975596825MaRDI QIDQ2484539FDOQ2484539

Authors: Shahar Mendelson, Alain Pajor, Nicole Tomczak-Jaegermann 

Publication date: 1 August 2005

Published in: Comptes Rendus. Mathématique. Académie des Sciences, Paris (Search for Journal in Brave)

Abstract: We present a randomized method to approximate any vector $v$ from some set $Tsubset{R}^n$. The data one is given is the set $T$, and $k$ scalar products $(inr{X}_i,v{)}_{i=1}^k$, where $(X_i{)}_{i=1}^k$ are i.i.d. isotropic subgaussian random vectors in $R^n$, and $klln$. We show that with high probability, any $yinT$ for which $(inr{X}_i,y{)}_{i=1}^k$ is close to the data vector $(inr{X}_i,v{)}_{i=1}^k$ will be a good approximation of $v$, and that the degree of approximation is determined by a natural geometric parameter associated with the set $T$. We also investigate a random method to identify exactly any vector which has a relatively short support using linear subgaussian measurements as above. It turns out that our analysis, when applied to $-1,1$-valued vectors with i.i.d, symmetric entries, yields new information on the geometry of faces of random $-1,1$-polytope; we show that a $k$-dimensional random $-1,1$-polytope with $n$ vertices is $m$-neighborly for very large $mleck/log(c^{\prime }n/k)$. The proofs are based on new estimates on the behavior of the empirical process $su{p}_{finF}|k^{-1}su{m}_{i=1}^k{f}^2(X_i)-E{f}^2|$ when $F$ is a subset of the $L_2$ sphere. The estimates are given in terms of the $gamm{a}_2$ functional with respect to the $ps{i}_2$ metric on $F$, and hold both in exponential probability and in expectation.

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

Recommendations

• Reconstruction and subgaussian operators in asymptotic geometric analysis
• Uniform uncertainty principle for Bernoulli and subgaussian ensembles
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• On sparse reconstruction from Fourier and Gaussian measurements
• Nonuniform sparse recovery with subgaussian matrices

zbMATH Keywords

random projectionssub-Gaussian processes

Mathematics Subject Classification ID

Gaussian processes (60G15) Approximation by other special function classes (41A30) Probabilistic methods in Banach space theory (46B09)

Cites Work

• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Majorizing measures: The generic chaining
• Title not available (Why is that?)
• Geometric approach to error-correcting codes and reconstruction of signals
• Empirical processes and random projections
• Subspaces of Small Codimension of Finite-Dimensional Banach Spaces
• Title not available (Why is that?)
• Title not available (Why is that?)
• Regularization of star bodies by random hyperplane cut off
• Title not available (Why is that?)

Cited In (9)

• Reconstruction and subgaussian operators in asymptotic geometric analysis
• Robust width: a characterization of uniformly stable and robust compressed sensing
• Stable recovery and the coordinate small-ball behaviour of random vectors
• Uniform uncertainty principle for Bernoulli and subgaussian ensembles
• Stability and instance optimality for Gaussian measurements in compressed sensing
• Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling
• From low- to high-dimensional moments without magic
• On weakly bounded empirical processes
• Title not available (Why is that?)

This page was built for publication: Reconstruction and subgaussian processes

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