Consider the problem of sparse principal component analysis: $$\max_{||{\bf x}||_0=k,||{\bf x}||_2=1} {\bf x}^T{\bf A}{\bf x}$$ where a $k$-sparse $n$-dim. unit vector that "maximizes variance" is to be found. I was wondering if there were any practical (i.e. not artificial :)) examples where the correlation matrix ${\bf A}$ has fixed and low rank, or it is a low rank update, i.e. ${\bf A} = c{\bf I}+{\bf C}{\bf C}^T$, where $c$ is a constant and ${\bf C}$ has low and fixed rank independent of $n$.

thank you


Most examples of principal component analysis are of the type you describe (since people usually want to know the (eg) top three principal components). Look at SVDPACK or PROPACK.

Edit It is true that I missed the requirement that the vector itself be sparse. In that case, you might want to look at OptSpace.

| cite | improve this answer | |
  • 1
    $\begingroup$ ...but in general, the actual principal vectors won't be sparse, so Anadim's problem doesn't seem reduce to standard principal component analysis. $\endgroup$ – Darsh Ranjan Feb 12 '11 at 1:02
  • $\begingroup$ I was trying to find practical models where the covariance is extremely (i.e. 2 or 3) low rank plus a scaled identity. This can be interpreted as some small number of hidden variables generating a tall random vector plus i.i.d. noise. Now why would we care for sparse vectors that maximize variance? Because they are cheaper to store and much easier to interpret. There is a whole literature on that kind of problems referred to as the sparse principal component analysis. $\endgroup$ – Anadim Feb 25 '11 at 4:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.