Change search
ReferencesLink to record
Permanent link

Direct link
On the Theorem of Uniform Recovery of Random Sampling Matrices
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
2014 (English)In: IEEE Transactions on Information Theory, ISSN 0018-9448, Vol. 60, no 3, 1700-1710 p.Article in journal (Refereed) Published
Abstract [en]

We consider two theorems from the theory of compressive sensing. Mainly a theorem concerning uniform recovery of random sampling matrices, where the number of samples needed in order to recover an s-sparse signal from linear measurements (with high probability) is known to be m greater than or similar to s(ln s)(3) ln N. We present new and improved constants together with what we consider to be a more explicit proof. A proof that also allows for a slightly larger class of m x N-matrices, by considering what is called effective sparsity. We also present a condition on the so-called restricted isometry constants, delta s, ensuring sparse recovery via l(1)-minimization. We show that delta(2s) < 4/root 41 is sufficient and that this can be improved further to almost allow for a sufficient condition of the type delta(2s) < 2/3.

Place, publisher, year, edition, pages
2014. Vol. 60, no 3, 1700-1710 p.
Keyword [en]
Bounded orthogonal systems, compressive sensing, effective sparsity, l(1)-minimization, random sampling matrices, restricted isometry property
National Category
Signal Processing Other Mathematics Computational Mathematics
URN: urn:nbn:se:kth:diva-141831DOI: 10.1109/TIT.2014.2300092ISI: 000331902400026ScopusID: 2-s2.0-84896839927OAI: diva2:698794

QC 20140228

Available from: 2014-02-25 Created: 2014-02-25 Last updated: 2014-03-28Bibliographically approved
In thesis
1. On Invertibility of the Radon Transform and Compressive Sensing
Open this publication in new window or tab >>On Invertibility of the Radon Transform and Compressive Sensing
2014 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

This thesis contains three articles. The first two concern inversion andlocal injectivity of the weighted Radon transform in the plane. The thirdpaper concerns two of the key results from compressive sensing.In Paper A we prove an identity involving three singular double integrals.This is then used to prove an inversion formula for the weighted Radon transform,allowing all weight functions that have been considered previously.Paper B is devoted to stability estimates of the standard and weightedlocal Radon transform. The estimates will hold for functions that satisfy an apriori bound. When weights are involved they must solve a certain differentialequation and fulfill some regularity assumptions.In Paper C we present some new constant bounds. Firstly we presenta version of the theorem of uniform recovery of random sampling matrices,where explicit constants have not been presented before. Secondly we improvethe condition when the so-called restricted isometry property implies the nullspace property.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2014. vii, 30 p.
TRITA-MAT-A, 2014:02
Radon transform, invertibility, compressive sensing, stability estimates
National Category
Mathematical Analysis
Research subject
urn:nbn:se:kth:diva-141837 (URN)978-91-7501-998-7 (ISBN)
Public defence
2014-03-28, D3, Lindstedtsvägen 5, Stockholm, 13:00 (English)
Knut and Alice Wallenberg Foundation, KAW 2005.0098

QC 20140228

Available from: 2014-02-28 Created: 2014-02-25 Last updated: 2014-02-28Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Andersson, JoelStrömberg, Jan-Olov
By organisation
Mathematics (Div.)
In the same journal
IEEE Transactions on Information Theory
Signal ProcessingOther MathematicsComputational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 58 hits
ReferencesLink to record
Permanent link

Direct link