Restricted isometry property for matrices whose entries are random variables belonging to some Orlicz spaces

Author:
V. B. Troshki

Translated by:
N. Semenov

Original publication:
Teoriya Imovirnostei ta Matematichna Statistika, tom **91** (2014).

Journal:
Theor. Probability and Math. Statist. **91** (2015), 193-203

MSC (2010):
Primary 68P30; Secondary 68W20

Published electronically:
February 4, 2016

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A new approach to the signal processing called compressive sensing has been extensively developed during the last few years. There are many papers devoted to this topic but the problem of constructing the universal measurement matrix has not yet been solved. We propose to use a matrix whose entries are random variables belonging to some Orlicz spaces as a measurement matrix. We prove that the matrix with such entries satisfies the so-called restricted isometry property which is one of the main concepts in compressive sensing.

**1.**B. S. Kašin,*The widths of certain finite-dimensional sets and classes of smooth functions*, Izv. Akad. Nauk SSSR Ser. Mat.**41**(1977), no. 2, 334–351, 478 (Russian). MR**0481792****2.**A. Yu. Garnaev and E. D. Gluskin,*The widths of a Euclidean ball*, Dokl. Akad. Nauk SSSR**277**(1984), no. 5, 1048–1052 (Russian). MR**759962****3.**Emmanuel J. Candes and Terence Tao,*Decoding by linear programming*, IEEE Trans. Inform. Theory**51**(2005), no. 12, 4203–4215. MR**2243152**, 10.1109/TIT.2005.858979**4.**David L. Donoho,*Compressed sensing*, IEEE Trans. Inform. Theory**52**(2006), no. 4, 1289–1306. MR**2241189**, 10.1109/TIT.2006.871582**5.**P. Wojtaszczyk,*Stability and instance optimality for Gaussian measurements in compressed sensing*, Found. Comput. Math.**10**(2010), no. 1, 1–13. MR**2591836**, 10.1007/s10208-009-9046-4**6.**Richard Baraniuk, Mark Davenport, Ronald DeVore, and Michael Wakin,*A simple proof of the restricted isometry property for random matrices*, Constr. Approx.**28**(2008), no. 3, 253–263. MR**2453366**, 10.1007/s00365-007-9003-x**7.**Ronald DeVore, Guergana Petrova, and Przemyslaw Wojtaszczyk,*Instance-optimality in probability with an 𝑙₁-minimization decoder*, Appl. Comput. Harmon. Anal.**27**(2009), no. 3, 275–288. MR**2559727**, 10.1016/j.acha.2009.05.001**8.**Yu. Mlavets',*A relationship between the Orlicz spaces of random variables and spaces*, Naukovyi Visnyk Uzhgorod. Univ. Ser. Matem. Inform.**25**(2014), no. 1, 77-84. (Ukrainian)**9.**V. V. Buldygin and Yu. V. Kozachenko,*Metric characterization of random variables and random processes*, Translations of Mathematical Monographs, vol. 188, American Mathematical Society, Providence, RI, 2000. Translated from the 1998 Russian original by V. Zaiats. MR**1743716****10.**Yu. V. Kozachenko and Yu. Yu. Mlavets′,*The Banach spaces of 𝐹_{𝜓}(Ω) of random variables*, Teor. Ĭmovīr. Mat. Stat.**86**(2011), 92–107 (Ukrainian, with English, Russian and Ukrainian summaries); English transl., Theory Probab. Math. Statist.**86**(2013), 105–121. MR**2986453**, 10.1090/S0094-9000-2013-00892-8**11.**George G. Lorentz, Manfred v. Golitschek, and Yuly Makovoz,*Constructive approximation*, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 304, Springer-Verlag, Berlin, 1996. Advanced problems. MR**1393437**

Retrieve articles in *Theory of Probability and Mathematical Statistics*
with MSC (2010):
68P30,
68W20

Retrieve articles in all journals with MSC (2010): 68P30, 68W20

Additional Information

**V. B. Troshki**

Affiliation:
Department of Probability Theory and Mathematical Analysis, Faculty of Mathematics, Uzhgorod National University, Universytets’ka Street, 14, Uzhgorod 88000, Ukraine

Email:
btroshki@ukr.net

DOI:
https://doi.org/10.1090/tpms/977

Keywords:
Orlicz space,
restricted isometry property,
compressive sensing

Received by editor(s):
September 9, 2014

Published electronically:
February 4, 2016

Article copyright:
© Copyright 2016
American Mathematical Society