Reconstruction and subgaussian processes

Shahar Mendelson; Alain Pajor; Nicole Tomczak-Jaegermann

doi:10.1016/j.crma.2005.04.032

Reconstruction and subgaussian processes

Shahar Mendelson^*, Alain Pajor, Nicole Tomczak-Jaegermann

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

13 Citations (Scopus)

Abstract

This Note presents a randomized method to approximate any vector v from some set T ⊂ ℝⁿ. The data one is given is the set T, and k scalar products (〈X_i, v〉)_i=1 ^k, where (X_i)_i=1^k are i.i.d. isotropic subgaussian random vectors in ℝⁿ, and k ≪ n. We show that with high probability any y ∈ T for which (〈X_i, y〉)_i=1^k is close to the data vector (〈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. This extends and improves recent results by Candes and Tao.

Original language	English
Pages (from-to)	885-888
Number of pages	4
Journal	Comptes Rendus Mathematique
Volume	340
Issue number	12
DOIs	https://doi.org/10.1016/j.crma.2005.04.032
Publication status	Published - 15 Jun 2005

Access to Document

10.1016/j.crma.2005.04.032

Cite this

@article{45d14045651c45f58c387b763adbc201,

title = "Reconstruction and subgaussian processes",

abstract = "This Note presents a randomized method to approximate any vector v from some set T ⊂ ℝn. The data one is given is the set T, and k scalar products (〈Xi, v〉)i=1 k, where (Xi)i=1k are i.i.d. isotropic subgaussian random vectors in ℝn, and k ≪ n. We show that with high probability any y ∈ T for which (〈Xi, y〉)i=1k is close to the data vector (〈Xi, v〉)i=1k 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. This extends and improves recent results by Candes and Tao.",

author = "Shahar Mendelson and Alain Pajor and Nicole Tomczak-Jaegermann",

year = "2005",

month = jun,

day = "15",

doi = "10.1016/j.crma.2005.04.032",

language = "English",

volume = "340",

pages = "885--888",

journal = "Comptes Rendus Mathematique",

issn = "1631-073X",

publisher = "Academie des sciences",

number = "12",

}

TY - JOUR

T1 - Reconstruction and subgaussian processes

AU - Mendelson, Shahar

AU - Pajor, Alain

AU - Tomczak-Jaegermann, Nicole

PY - 2005/6/15

Y1 - 2005/6/15

N2 - This Note presents a randomized method to approximate any vector v from some set T ⊂ ℝn. The data one is given is the set T, and k scalar products (〈Xi, v〉)i=1 k, where (Xi)i=1k are i.i.d. isotropic subgaussian random vectors in ℝn, and k ≪ n. We show that with high probability any y ∈ T for which (〈Xi, y〉)i=1k is close to the data vector (〈Xi, v〉)i=1k 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. This extends and improves recent results by Candes and Tao.

AB - This Note presents a randomized method to approximate any vector v from some set T ⊂ ℝn. The data one is given is the set T, and k scalar products (〈Xi, v〉)i=1 k, where (Xi)i=1k are i.i.d. isotropic subgaussian random vectors in ℝn, and k ≪ n. We show that with high probability any y ∈ T for which (〈Xi, y〉)i=1k is close to the data vector (〈Xi, v〉)i=1k 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. This extends and improves recent results by Candes and Tao.

UR - http://www.scopus.com/inward/record.url?scp=21344455943&partnerID=8YFLogxK

U2 - 10.1016/j.crma.2005.04.032

DO - 10.1016/j.crma.2005.04.032

M3 - Article

SN - 1631-073X

VL - 340

SP - 885

EP - 888

JO - Comptes Rendus Mathematique

JF - Comptes Rendus Mathematique

IS - 12

ER -

Reconstruction and subgaussian processes

Abstract

Access to Document

Other files and links

Fingerprint

Cite this