NP-Hardness and Inapproximability of Sparse PCA

On lines and planes of closest fit to systems of points in space

K. Pearson · 1901

Earlier work this paper cites.

Spektren endlicher grafen

L. Collatz and U. Sinogowitz · 1957

Earlier work this paper cites.

The varimax criterion for analytic rotation in factor analysis

H. Kaiser · 1958

Earlier work this paper cites.

Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis

J. Kruskal · 1964

Earlier work this paper cites.

A nonlinear mapping for data structure analysis

J. Sammon · 1969

Earlier work this paper cites.

A bound on the spectral radius of graphs

Y. Hong · 1988

Earlier work this paper cites.

Loadings and correlations in the interpretation of principal components

J. Cadima and I. Jolliffe · 1995

Cited alongside, same era.

Sparse approximate solutions to linear systems

B. Natarajan · 1995

Cited alongside, same era.

A modified principal component technique based on the lasso

N. Trendafilov, I. T. Jolliffe, and M. Uddin · 2003

Cited alongside, same era.

Generalized spectral bounds for sparse LDA

B. Moghaddam, Y. Weiss, and S. Avidan · 2006

Cited alongside, same era.

Sparse principal component analysis

H. Zou, T. Hastie, and R. Tibshirani · 2006

Cited alongside, same era.

A direct formulation for sparse PCA using semidefinite programming

A. d’Aspremont, L. El Ghaoui, M. I. Jordan, and G. R. G. Lanckriet · 2007

Cited alongside, same era.

Inapproximability of densest

Optimal solutions for sparse principal component analysis

A. d’Aspremont, F. Bach, and L. E. Ghaoui · 2008

Later among the works it cites.

Sparse regression as a sparse eignvalue problem

B. Moghaddam, A. Gruber, Y. Weiss, and S. Avidan · 2008

Later among the works it cites.

Sparse principal component analysis via regularized low rank matrix approximation

H. Shen and J. Z. Huang · 2008

Later among the works it cites.

Non-negative sparse PCA with provable guarantees

M. Asteris, D. Papailiopoulos, and A. Dimakis · 2014

Later among the works it cites.

Variable selection is hard

Original

D. Foster, H. Karloff, and J. Thaler · 2014

Later among the works it cites.