On Support Recovery with Sparse CCA: Information Theoretic and Computational Limits

In this paper, we consider asymptotically exact support recovery in the context of high dimensional and sparse Canonical Correlation Analysis (CCA). Our main results describe four regimes of interest based on information theoretic and computational considerations. In regimes of "low" spars...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2023-03, Vol.69 (3), p.1-1
Main Authors: Laha, Nilanjana, Mukherjee, Rajarshi
Format: Article
Language:English
Subjects:
Asymptotic properties
Canonical Correlation Analysis
Correlation
Correlation analysis
Covariance matrices
Estimation
High Dimension
Information theory
Input variables
Low Degree Polynomials
Lower bounds
Polynomials
Principal component analysis
Recovery
Sparsity
Support Recovery
Surges
Throughput
Variable Selection
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we consider asymptotically exact support recovery in the context of high dimensional and sparse Canonical Correlation Analysis (CCA). Our main results describe four regimes of interest based on information theoretic and computational considerations. In regimes of "low" sparsity we describe a simple, general, and computationally easy method for support recovery, whereas in a regime of "high" sparsity, it turns out that support recovery is information theoretically impossible. For the sake of information theoretic lower bounds, our results also demonstrate a non-trivial requirement on the "minimal" size of the nonzero elements of the canonical vectors that is required for asymptotically consistent support recovery. Subsequently, the regime of "moderate" sparsity is further divided into two sub-regimes. In the lower of the two sparsity regimes, we show that polynomial time support recovery is possible by using a sharp analysis of a co-ordinate thresholding [1] type method. In contrast, in the higher end of the moderate sparsity regime, appealing to the "Low Degree Polynomial" Conjecture [2], we provide evidence that polynomial time support recovery methods are inconsistent. Finally, we carry out numerical experiments to compare the efficacy of various methods discussed.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2022.3214201