4
$\begingroup$

I have data measuring two events in space and in time. More precisely, I have two rectangular data matrices $A$ and $B$ which both have $20$ time rows and $1\text{M}$ space columns.

I want to analyse the interaction between these two events. In particular, I want to do a Canonical-Correlation Analysis (CCA) on their product. I could calculate the product $A^{T}B$, which is a large $1\text{M}$ by $1\text{M}$ matrix. Or I could calculate $BA^{T}$, which is a small $20$ by $20$ matrix.

I know the rank of both types of products is the same (see Math Stack Exchange). This leads me to think the resolution of the information contained in both products is the same. I also know that the eigenvalues for $A^{T}B$ and $BA^{T}$ are identical (see Math Stack Exchange). However, the singular values need not be the same (see Math Stack Exchange).

Is there a way to exploit these facts to analyse the smaller $BA^{T}$ product and still get all relevant information about the large $A^{T}B$ product? Relevant in terms of the CCA. In particular, I would like to avoid the computationally intensive SVD of $A^{T}B$, yet still determine its Principal Components.

$\endgroup$
6
  • 1
    $\begingroup$ What exactly is amount of information in matrix (or in product of matrixes)? $\endgroup$ – Nik Oct 2 '17 at 9:53
  • $\begingroup$ @Nik I am not sure about a precise formulation, but my intuition tells me it is related to the number of elements which can vary independently. Therefore, related to the rank and to the (number of) eigenvalues. If anyone can make this more precise, or give a counter-example, that would be helpful. $\endgroup$ – LBogaardt Oct 2 '17 at 9:56
  • 1
    $\begingroup$ I think it's entirely clear what you mean by AB and BA, however there should be some transposes in there somewhere so that matrices are composable. $\endgroup$ – James Griffin Oct 2 '17 at 9:56
  • 3
    $\begingroup$ The "amount of information" is not the same. Consider A and B with only row. One product would just give the dot product, the other product would be the outer product which contains the information about the directions of both A and B (though loses their individual magnitudes). The amount of information you're interested in might be the same of course. $\endgroup$ – James Griffin Oct 2 '17 at 10:01
  • $\begingroup$ @JamesGriffin Okay :) Though the eigenvalues are still the same. Can this be exploited somehow? $\endgroup$ – LBogaardt Oct 2 '17 at 10:54
1
$\begingroup$

The following does not answer the OP's question directly, but does solve the issue of performing an SVD on a large matrix product $AB$. This is based on https://arxiv.org/abs/0909.4061v2 and its references.

The large rectangular $m \times n$ matrices $A$ and $B$ with $n << m$ can be projected to a subspace of dimensions equal to the smallest side, $n$, without losing much/any of its action.

In the case of the OP, $A$ and $B$ are both $20 \times 10\text{M}$, while the new $\tilde{A}$ and $\tilde{B}$ are only $20 \times 20$.

Steps:

  • Generate two random $n \times n$ matrices $\Omega_i$ from a Gaussian distribution with $\mu = 0$ and $\sigma = 1$
  • Form the $m \times n$ matrix $Y_1 = AΩ_1$
  • Form the $m \times n$ matrix $Y_2 = BΩ_2$
  • Construct two $m \times n$ matrices $Q_i$ whose columns form an orthonormal basis for the range of $Y_i$, e.g. using the QR factorization $Y_i = Q_iR_i$
  • Form the $n \times n$ matrix $\tilde{A} = Q_1^{∗}A$
  • Form the $n \times n$ matrix $\tilde{B} = Q_2^{∗}B$

Now, the product $\tilde{A} \tilde{B}$ is $n \times n$. The singular values for this product are very close to the largest singular values of the product $AB$.

The difference between the real $A$ and its approximation $\tilde{A}$ is given by $||A-Q_1\tilde{A}||$. Likewise for $B$.

I do not have proof of exactly this, though similar steps are proven in the reference above. I am not sure this will work in all cases, but some quick tests seem to suggest it works.

$\endgroup$

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.