Sparse CCA: adaptive estimation and computational barriers (Q1687119)

This paper considers adaptive minimax and computationally tractable estimation of leading sparse canonical coefficient vectors in high dimensions. Assume that \(X\in\mathbb{R}^p\) and \(Y\in\mathbb{R}^m\) are random vectors. Let the linear combinations \((u_j'X, v_j'Y)\) be the \(j\)th pair of canonical variates. Suppose that there are \(r\) pairs of canonical coefficient vectors (and canonical variates) among the two sets of variables. Denote \({U}=[{u}_1,\dots,{u}_r]\) and \({V}=[{v}_1,\dots,v_r]\). Instead of considering the joint loss \(\|\hat{{U}}\hat{{V}}'-{{U}}{{V}}\|\) of the estimation \(\hat{{U}}\) and \(\hat{{V}}\) of \(U\) and \(V\), this paper provides a finer analysis by studying individual estimation errors of \(U\) and \(V\) under a natural loss function that can be interpreted as prediction error of canonical variates. Under a Gaussian canonical pair model, it first establishes separate minimax estimation rates for canonical coefficient vectors of each set of random variables under no structural assumption on marginal covariance matrices. Second, it proposes a computationally feasible estimator to attain the optimal rates adaptively under an additional sample size condition. Finally, it shows that a sample size condition of this kind is needed for any randomized polynomial-time estimator to be consistent, assuming hardness of certain instances of the planted clique detection problem. As a byproduct, the first computational lower bounds is obtained for sparse PCA under the Gaussian single spiked covariance model.