1
$\begingroup$

Say one is given a matrix (assume real and symmetric if necessary) and its $n-$dimensional columns be say $v_1,v_2,..,v_n$. Now is it possible to find a set of $d<n$ lower dimensional vectors ($w_1,..,w_d$) such that they form a $d \times d$ matrix $B$ (assume real and symmetric) with either of these properties,

  • That the $d$ eigenvalues of $B$ are "close" to the top$-d$ eigenvalues of $A$? (and hence the correspomding eigenvectors are also "close" in some sense?)

  • That the spectral norm of $B$ is "close" to the spectral norm of $A$.


Will this be called "sketching"? Does Johnson-Lindenenstrauss lemma help in doing these?

$\endgroup$
1
$\begingroup$

Yes, you can match the eigenvalues. It is easy to construct a matrix with any desired eigenvalues: for instance, create a diagonal matrix and put the desired values on the diagonal. Thus, you can get an exact match, not just an approximate match. Nothing fancy is needed.

No, matching the eigenvalues doesn't imply that the eigenvectors of $B$ are somehow related in any way to the eigenvectors of $A$.

Given a value $n$ you can easily construct a matrix $B$ whose spectral norm is $n$, so that too can be exactly matched.

You don't need the Johnson–Lindenstrauss lemma for these results.

$\endgroup$
  • $\begingroup$ You are reading the question in a very trivial way - may be my framing of the question was bad! I mean I want to match both - the eigenvectors and the eigenvalues both need to be as close. $\endgroup$ – Anirbit Apr 3 '16 at 3:56

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.