How to project a vector onto a very large, non-orthogonal subspace

Question

I have a difficult problem.

I have a very large, non-orthogonal matrix $A$ and need to project the vector $y$ onto the subspace spanning the columns of $A$. If this were a small matrix, I would use Gram-Schmidt or just compute $A(A^TA)^{-1}A^Ty$. Unfortunately, $A$ is just too big to do this in a feasible amount of time. Is there a good trick to do this projection?

EDIT2: Some background info: I work in signal processing and work with Fusion Frames quite a bit. For those unfamiliar, it is the problem of representing a signal with a union of subspaces from an overcomplete dictionary, typically using a block-sparse solver (in my case, a program called SPGL1). The problem is, I need to project my signal vector onto this dictionary before performing the inversion. The dictionary is coherent so under normal circumstances I need to use the formula above or a method like Gram-Schmidt to get an orthonormal basis.

Right now, my working solution is to approximate this projection by using the truncated SVD and using the $U$ matrix as an approximate orthonormal basis (a la PCA). But, it would be nice if anyone knew any iterative projection algorithms. I know this isn't a scientific computing site, but I figured there may be someone here who knows some linear algebra tricks.

Answer 1

Depending on how many rows, maybe you could use some statistics results.

When I was doing Principal Component Analysis I ended up having a matrix $X_{75\times 375000}$ and I could still find a good vector space that described well these vectors (and projections).

That's the whole point of Principal Component Analysis. Since the amount of information you have is just too much, you can get rid of some redundancy and reduce the dimension (really, my case was a 75 dimension space with that huge matrix).

Maybe these articles can give you the basic idea. http://www.cs.otago.ac.nz/cosc453/student_tutorials/principal_components.pdf http://www.stat.cmu.edu/~cshalizi/490/pca/pca-handout.pdf

It's a well known algorithm, mainly for computer vision (Eigenfaces). Maybe it won't be useful at all, since you want the span of these vectors and this is an approximation method. Anyway, I always consider this algorithm when some gigantic vectors need to be analyzed.

Answer 2

It makes a considerable difference if you need to project a vector just once or repeatedly inside some loop of another algorithm. If you would be in the latter case than it would be indeed a good idea to follow suv...rits suggestion and use an iterative algorithm to solve the normal equations (conjugate gradients, probably with preconditioning, suggest themselves). In this case you can often just use a small and fixed number of CG iterations and restart the next CG iteration with what you've got from the previous run. If the point you want to project does not change very much in the outer loop, CG should be converging eventually.

However, your EDIT2 suggests that your only project you data once. Without knowing your precise approximation problem, it could be possible to make a reformulation of the problem: If $y$ is your signal but you need to put $z = A(A^T A)^{-1}A^Ty$ in your algorithm, you could just put in $z$ and add the constraints $z = Aw$ and $A^T Aw = A^T y$, i.e. you introduce two new variables and two new linear constraints. Then use some algorithm for your new inversion which can handle linear constraints. Without knowing more details I can't be more concrete here…