NDLI: Simultaneous Support Recovery in High Dimensions: Benefits and Perils of Block <formula formulatype=inline><tex Notation=TeX>$ell _{1}/ell

Content Provider	IEEE Xplore Digital Library
Author	Negahban, S.N. Wainwright, M.J.
Copyright Year	1963
Abstract	Given a collection of r ≥ 2 linear regression problems in p dimensions, suppose that the regression coefficients share partially common supports of size at most s. This set-up suggests the use of ℓ₁/ℓ_∞-regularized regression for joint estimation of the p×r matrix of regression coefficients. We analyze the high-dimensional scaling of ℓ₁/ℓ_∞-regularized quadratic programming, considering both consistency rates in ℓ_∞-norm, and how the minimal sample size n required for consistent variable selection scales with model dimension, sparsity, and overlap between the supports. We first establish bounds on the ℓ_∞-error as well sufficient conditions for exact variable selection for fixed design matrices, as well as for designs drawn randomly from general Gaussian distributions. Specializing to the case r = 2 linear regression problems with standard Gaussian designs whose supports overlap in a fraction α ∈ [0,1] of their entries, we prove that ℓ₁/ℓ_∞-regularized method undergoes a phase transition characterized by the rescaled sample size θ_1,∞(n, p, s, α) = n/{(4 - 3 α) s log(p-(2- α) s)}. An implication is that the use of ℓ₁/ℓ_∞-regularization yields improved statistical efficiency if the overlap parameter is large enough ( α >; 2/3), but has worse statistical efficiency than a naive Lasso-based approach for moderate to small overlap (α <; 2/3 ). Empirical simulations illustrate the close agreement between theory and actual behavior in practice. These results show that caution must be exercised in applying ℓ₁/ℓ_∞ block regularization: if the data does not match its structure very closely, it can impair statistical performance relative to computationally less expensive schemes.
Sponsorship	IEEE Information Theory Society
Starting Page	3841
Ending Page	3863
Page Count	23
File Size	894000
File Format	PDF
ISSN	00189448
Volume Number	57
Issue Number	6
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2011-06-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Input variables Estimation Symmetric matrices Multivariate regression Joints Noise Linear regression subset selection $\ell _{1}$-constraints compressed sensing convex relaxation group Lasso high-dimensional inference model selection phase transitions sparse approximation
Content Type	Text
Resource Type	Article
Subject	Library and Information Sciences Information Systems Computer Science Applications

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

Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $ell _{1}$ -Constrained Quadratic Programming (Lasso)

Information-Theoretic Limits on Sparse Signal Recovery: Dense versus Sparse Measurement Matrices

Compressed and Privacy-Sensitive Sparse Regression

Simultaneously Structured Models With Application to Sparse and Low-Rank Matrices

Simultaneous support recovery in high dimensions: Benefits and perils of block $\ell_1/\ell_\infty$-regularization

Robust Lasso With Missing and Grossly Corrupted Observations

Sparse Recovery With Unknown Variance: A LASSO-Type Approach

Linear Regression With a Sparse Parameter Vector

Compressed Sensing Matrices From Fourier Matrices

Simultaneous Support Recovery in High Dimensions: Benefits and Perils of Block $ell _{1}/ell _{infty} $-Regularization

Similar Documents

Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $ell _{1}$ -Constrained Quadratic Programming (Lasso)

Information-Theoretic Limits on Sparse Signal Recovery: Dense versus Sparse Measurement Matrices

Compressed and Privacy-Sensitive Sparse Regression

Simultaneously Structured Models With Application to Sparse and Low-Rank Matrices

Simultaneous support recovery in high dimensions: Benefits and perils of block $\ell_1/\ell_\infty$-regularization

Robust Lasso With Missing and Grossly Corrupted Observations

Sparse Recovery With Unknown Variance: A LASSO-Type Approach

Linear Regression With a Sparse Parameter Vector

Compressed Sensing Matrices From Fourier Matrices

Simultaneous Support Recovery in High Dimensions: Benefits and Perils of Block $ell _{1}/ell _{infty} $-Regularization