Probabilistic algorithms for matrix approximation

Considering regular matrix approximation inequality

|| $A - QQ^TA$|| < e

where we try to approximate matrix $A$ by a lower rank orthonormal matrix $Q$. I've read an article on probabilistic algorithms for such an purpose. You simply pick random (Gaussian etc.) vectors $\omega$, then generate vectors from the range of $A$ by $y =A\omega$. Finally, construct $Q$ by these vectors, $y$, after Gram-Schmidt etc. Details can be found in "Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions".

My question is the following:

Let's assume we have several matrices $A_i$ with "same structure" and each have the same rank $k$. I may give details on the structure if you interest. And we find $Q_i$ for each corresponding matrix $A_i$. Again assume we may define a distribution over $Q_i$ depending on the distribution we use during approximating matrices $Q_i$ (the distribution of $\omega$).

Then, we get a new matrix $A$ with again same structure and rank $k$. But this time we only have a submatrix $A(:,J)$ i.e. only several columns. I want to approximate $Q$ for this new matrix using only given columns.

To summarize we have two phase:
1. We somehow learn a model for $Q$ using given full matrices $A_i$
2. Given a subsample $A(:,J)$ of a novel matrix $A$ (that is not present in the first phase), we derive its corresponding $Q$

I hope, you may simply recommend me some useful references. I do not even know where to look.

• Is there a reason to not just use the Q from the (pivoted) QR factorization of $A(:,J)$? Or is your goal to use information from the $Q_i$'s to improve on said $Q$? – Jack Poulson Jan 10 '12 at 19:06
• Yes, information from the $Q_i$'s is used to improve $Q$. We may have only a few columns of A (i.e. J includes only a few); therefore, it is not possible to use QR. Let's say we know that A has N columns just same as previous $A_i$'s, yet we are given only $n << N$ columns for A. – ahmethungari Jan 11 '12 at 23:42
• Exactly, I need to span N dimensional space just like previous $Q_i$'s. The missing information should be provided from prior distributions. – ahmethungari Jan 12 '12 at 8:14
• A CORRECTION: We try to span $k$ dimensional space (rank of the matrix), not $N$ dimensional space. Then the "$n << N$" in the second comment should be $n << k$. Hence, we try find a $Q$ with exactly $k$ columns. – ahmethungari Jan 12 '12 at 11:03