Restricted isometry property for matrices whose entries are random variables belonging to some Orlicz spaces $L_U(\Omega )$
Author:
V. B. Troshki
Translated by:
N. Semenov
Journal:
Theor. Probability and Math. Statist. 91 (2015), 193-203
MSC (2010):
Primary 68P30; Secondary 68W20
DOI:
https://doi.org/10.1090/tpms/977
Published electronically:
February 4, 2016
MathSciNet review:
3364134
Full-text PDF Free Access
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 $L_U(\Omega )$ 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.
References
- 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
- 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
- Emmanuel J. Candes and Terence Tao, Decoding by linear programming, IEEE Trans. Inform. Theory 51 (2005), no. 12, 4203–4215. MR 2243152, DOI https://doi.org/10.1109/TIT.2005.858979
- David L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory 52 (2006), no. 4, 1289–1306. MR 2241189, DOI https://doi.org/10.1109/TIT.2006.871582
- P. Wojtaszczyk, Stability and instance optimality for Gaussian measurements in compressed sensing, Found. Comput. Math. 10 (2010), no. 1, 1–13. MR 2591836, DOI https://doi.org/10.1007/s10208-009-9046-4
- 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, DOI https://doi.org/10.1007/s00365-007-9003-x
- Ronald DeVore, Guergana Petrova, and Przemyslaw Wojtaszczyk, Instance-optimality in probability with an $l_1$-minimization decoder, Appl. Comput. Harmon. Anal. 27 (2009), no. 3, 275–288. MR 2559727, DOI https://doi.org/10.1016/j.acha.2009.05.001
- Yu. Mlavets’, A relationship between the Orlicz spaces of random variables and spaces $\mathbf {F}_\psi (\Omega )$, Naukovyi Visnyk Uzhgorod. Univ. Ser. Matem. Inform. 25 (2014), no. 1, 77–84. (Ukrainian)
- 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
- Yu. V. Kozachenko and Yu. Yu. Mlavets′, The Banach spaces of ${\bf F}_\psi (\Omega )$ 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, DOI https://doi.org/10.1090/S0094-9000-2013-00892-8
- 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
References
- B. S. Kashin, The widths of some finite-dimensional sets and classes of smooth functions, Izv. Akad. Nauk SSSR. Ser. Mat. 41 (1977), 334–351; English transl. in Math. USSR-Izvestiya 11 (1977), 317–333. MR 0481792 (58:1891)
- A. Yu. Garnaev and E. Gluskin, The width of a Euclidean ball, Dokl. AN SSSR 277 (1984), 1048–1052. (Russian) MR 759962 (85m:46023)
- E. Candes and T. Tao, Decoding by linear programming, IEEE Trans. Inform. Theory 51 (2005), 4203–4215. MR 2243152 (2007b:94313)
- D. Donoho, Compressed sensing, IEEE Trans. Inf. Theory 52 (2006), no. 4, 1289–1306. MR 2241189 (2007e:94013)
- P. Wojtaszczyk, Stability and instance optimality for Gaussian measurements in compressed sensing, Found. Comput. Math. 10(1) (2010), 1–13. MR 2591836 (2010m:94053)
- R. Baraniuk, M. Davenport, R. DeVore, and M. Wakin, A simple proof of the restricted isometry property for random matrices, Constr. Approx. 28 (2007), no. 3, 253–263. MR 2453366 (2010j:41035)
- R. DeVore, G. Petrova, and P. Wojtaszczyk, Instance-optimality in probability with an $\ell _1$-minimization decoder, Appl. Comput. Harmon. Anal. 27 (2009), 275–288. MR 2559727 (2010i:42060)
- Yu. Mlavets’, A relationship between the Orlicz spaces of random variables and spaces $\mathbf {F}_\psi (\Omega )$, Naukovyi Visnyk Uzhgorod. Univ. Ser. Matem. Inform. 25 (2014), no. 1, 77–84. (Ukrainian)
- V. Buldygin and Yu. Kozachenko, Metric Characterization of Random Variables and Random Processes, American Mathematical Society, Providence, RI, 2000. MR 1743716 (2001g:60089)
- Yu. V. Kozachenko and Yu. Yu. Mlavets’, The Banach spaces $F_\psi (\Omega )$ of random variables, Teor. Imovirnost. Matem. Statyst. 86 (2012), 92–107; English transl. in Theor. Probability and Math. Statist. 86 (2013), 105–121. MR 2986453
- G. Lorentz, M. von Golitschek, and Yu. Makovoz, Constructive Approximation: Advanced Problems, Grundlehren Math. Wiss., Springer-Verlag, Berlin, 1996. MR 1393437 (97k:41002)
Similar Articles
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
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
