Say one has a $D \times n$ matrix $A$ all of whose entries are non-zero. One wants a method which will look at each of the columns of $A$ one by one and create new $m \ll D $ dimensional columns and stack them up as a matrix $A'$ of dimension $m \times n$ such that

$$\|A^TA - A'^T A'\|_2 < \epsilon$$

for some given $\epsilon$.

Is this some standard questions that is known? It would be very helpful if someone could kindly point me to the closest available literature on this!

If one takes a SVD of $A$ and looks at the top $m$ left singular vectors say $\{ u_i \}_{i=1}^m$ and the top $m$ right singular vectors say $\{ v_i \}_{i=1}^m$ and the top $m$ singular values being $\{ \sigma_i \}_{i=1}^m$ then most likely for a given $m$ the best $A'$ is $A' = \sum_{i=1}^m \sigma_i u_i v_i^T$. But doing this calculation will take time polynomial in $D$ and $n$.

I am hoping if there are matrix sketching techniques or subspace learning techniques which will achieve this in $O(polylog(n,D))$ time.


Your Answer

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

Browse other questions tagged or ask your own question.