  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 non-zero 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, using a sharp analysis of a coordinate
thresholding (Deshpande and Montanari, 2014) type method, we show that
polynomial time support recovery is possible. In contrast, in the higher end of
the moderate sparsity regime, appealing to the "Low Degree Polynomial"
Conjecture (Kunisky et al., 2019), 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.
