4
$\begingroup$

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.

Thank you for your time.

$\endgroup$
  • 1
    $\begingroup$ 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$? $\endgroup$ – Jack Poulson Jan 10 '12 at 19:06
  • $\begingroup$ 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. $\endgroup$ – ahmethungari Jan 11 '12 at 23:42
  • $\begingroup$ I am confused as to your statement that QR cannot be used on tall skinny matrices, as that is where it is most efficient (both in serial and in parallel). Do you mean that you need Q to span more than an n-dimensional subspace? $\endgroup$ – Jack Poulson Jan 12 '12 at 0:57
  • $\begingroup$ Exactly, I need to span N dimensional space just like previous $Q_i$'s. The missing information should be provided from prior distributions. $\endgroup$ – ahmethungari Jan 12 '12 at 8:14
  • $\begingroup$ 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. $\endgroup$ – ahmethungari Jan 12 '12 at 11:03

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.