NDLI: Revisiting model selection and recovery of sparse signals using one-step thresholding

Content Provider	IEEE Xplore Digital Library
Author	Bajwa, W.U. Calderbank, R. Jafarpour, S.
Copyright Year	2010
Description	Author affiliation: Duke University, USA (Bajwa, W.U.; Calderbank, R.) \|\| Princeton University, USA (Jafarpour, S.)
Abstract	This paper studies non-asymptotic model selection and recovery of sparse signals in high-dimensional, linear inference problems. In contrast to the existing literature, the focus here is on the general case of arbitrary design matrices and arbitrary nonzero entries of the signal. In this regard, it utilizes two easily computable measures of coherence—termed as the worst-case coherence and the average coherence—among the columns of a design matrix to analyze a simple, model-order agnostic one-step thresholding (OST) algorithm. In particular, the paper establishes that if the design matrix has reasonably small worst-case and average coherence then OST performs near-optimal model selection when either (i) the energy of any nonzero entry of the signal is close to the average signal energy per nonzero entry or (ii) the signal-to-noise ratio (SNR) in the measurement system is not too high. Further, the paper shows that if the design matrix in addition has sufficiently small spectral norm then OST also exactly recovers most sparse signals whose nonzero entries have approximately the same magnitude even if the number of nonzero entries scales almost linearly with the number of rows of the design matrix. Finally, the paper also presents various classes of random and deterministic design matrices that can be used together with OST to successfully carry out near-optimal model selection and recovery of sparse signals under certain SNR regimes or for certain classes of signals.
Starting Page	977
Ending Page	984
File Size	544899
Page Count	8
File Format	PDF
ISBN	9781424482153
e-ISBN	9781424482160
DOI	10.1109/ALLERTON.2010.5707015
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2010-09-29
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Algorithm design and analysis Analytical models Computational modeling Coherence Sparse matrices Signal to noise ratio
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