NDLI: Efficient and stable recovery of Legendre-sparse polynomials

Content Provider	IEEE Xplore Digital Library
Author	Rauhut, H. Ward, R.
Copyright Year	2010
Description	Author affiliation: Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, 10012, USA (Ward, R.) \|\| Hausdorff Center for Mathematics and the Institute for Numerical Simulation, University of Bonn, Endenicher Allee 60, 53115, Germany (Rauhut, H.)
Abstract	We consider the recovery of polynomials that are sparse with respect to the basis of Legendre polynomials from a small number of random sampling points. We show that a Legendre s-sparse polynomial of maximal degree N can be recovered from m ≍ s $log^{4}(N)$ random samples that are chosen independently according to the Chebyshev probability measure $π^{Ȓ1}(1$ - $x^{2})^{Ȓ}dx$ on [Ȓ1; 1]. As an efficient recovery method, ℓ1-minimization can be used. We establish these results by showing the restricted isometry property of a preconditioned random Legendre matrix. Our results extend to a large class of orthogonal polynomial systems on [Ȓ1; 1]. As a byproduct, we obtain condition number estimates for preconditioned random Legendre matrices that should be of interest on their own.
Starting Page	1
Ending Page	6
File Size	452864
Page Count	6
File Format	PDF
ISBN	9781424474165
e-ISBN	9781424474172
DOI	10.1109/CISS.2010.5464911
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2010-03-17
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Greedy algorithms Minimization methods random matrices sparse recovery condition numbers Sparse matrices ℓ1-minimization Jacobian matrices Interpolation Tensile stress Chebyshev approximation Sampling methods Polynomials Iterative methods Legendre polynomials compressive sensing orthogonal polynomials
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Improved sparse recovery thresholds with two-step reweighted ℓ1 minimization

Sparse Signal Recovery via Optimized Orthogonal Matching Pursuit

Rapidly computing sparse Legendre expansions via sparse Fourier transforms

Sparse Legendre expansions via ℓ1-minimization

Greedy Orthogonal Matching Pursuit algorithm for sparse signal recovery in compressive sensing

Alternating minimization techniques for the efficient recovery of a sparsely corrupted low-rank matrix

Beyond ℓ-norm minimization for sparse signal recovery

Complex sparse projections for compressed sensing

An approximate L0 norm minimization algorithm for compressed sensing

Efficient and stable recovery of Legendre-sparse polynomials

Similar Documents

Improved sparse recovery thresholds with two-step reweighted ℓ1 minimization

Sparse Signal Recovery via Optimized Orthogonal Matching Pursuit

Rapidly computing sparse Legendre expansions via sparse Fourier transforms

Sparse Legendre expansions via ℓ1-minimization

Greedy Orthogonal Matching Pursuit algorithm for sparse signal recovery in compressive sensing

Alternating minimization techniques for the efficient recovery of a sparsely corrupted low-rank matrix

Beyond ℓ-norm minimization for sparse signal recovery

Complex sparse projections for compressed sensing

An approximate L0 norm minimization algorithm for compressed sensing

Efficient and stable recovery of Legendre-sparse polynomials