Collective Support Recovery for Multi-Design Multi-Response Linear Regression

Weiguang Wang, Yingbin Liang, Eric P. Xing

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


The multi-design multi-response linear regression problem is investigated, in which design matrices are Gaussian with covariance matrices Σ(1:K) = Σ(1), . . .,Σ(K) for K linear regression tasks. Design matrices across tasks are assumed to be independent. The support union of K p-dimensional regression vectors (collected as columns of matrix B∗) is recovered using l1/l2-regularized lasso. Sufficient and necessary conditions on sample complexity are characterized as a sharp threshold to guarantee successful recovery of the support union. This model has been previously studied via l1/l-regularized lassoand via l1/l1 + l1/l-regularized lasso, in which sharp threshold on sample complexity is characterized only for K = 2 and under special conditions. In this paper, using l1/l2-regularized lasso, sharp threshold on sample complexity is characterized under standard regularization conditions. Namely, if n > cp1Ψ(B∗,Σ(1:K)) log( p - s) where cp1 is a constant, and s is the size of the support set, then l1/l2-regularized lasso correctly recovers the support union; and if n > n > cp2Ψ(B∗,Σ(1:K)) log( p - s) where cp2 is a constant, then l1/l2-regularized lasso fails to recover the support union. In particular, the function Ψ(B∗,Σ(1:K)) captures the impact of the sparsity of K regression vectors and the statistical properties of the design matrices on the threshold on sample complexity. Therefore, such threshold function also demonstrates the advantages of joint support union recovery using multitask lasso over individual support recovery using single-task lasso.

Original languageEnglish (US)
Article number6967784
Pages (from-to)513-534
Number of pages22
JournalIEEE Transactions on Information Theory
Issue number1
StatePublished - Jan 1 2015


  • High dimensional feature selection
  • multi-task linear regression
  • sample complexity
  • sparsity

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'Collective Support Recovery for Multi-Design Multi-Response Linear Regression'. Together they form a unique fingerprint.

Cite this