Let $A$ and $B$ be matrices of dimensions $d \times n$. Let $C = AB^{\top}$.

We also know that $C = I \mathrm{diag}(\gamma) J$ for some matrices $I$ and $J$ and vector $\gamma$ of length $m$, $m < \min(d,n)$ (i.e. $I$ is of dimension $d \times m$ and $J$ is of dimension $m \times d$).

Using only the matrix $B^{\top}A$ (and not $AB^{\top}$, $I$, $J$ or $\gamma$), I want to find $U$ and $V$ of dimensions $m \times d$ such that $U I$ and $V J$ are invertible and $U A$ and $V B$ can be calculated. You can apply any decomposition or extract any information you need from $B^{\top} A$.

FIX: I also have $B^{\top} B$ and $A^{\top} A$ at my disposal.

EDIT: I managed to refine the question.

Let $\sigma(D)$ be the non-zero eigenvalues of a square matrix $D$ and let $s(C)$ be the non-zero singular values of a matrix $C$.

We know that if $C = AB^{\top}$, then:

$s^2(C) = \sigma(C C^{\top}) = \sigma(AB^{\top} B A^{\top}) = \sigma(A^{\top} A B^{\top} B)$

I am also assuming that I can compute $A^{\top} A$ and $B^{\top} B$, which means that $s^2(C)$ is computable.

I think $U$ and $V$ that I am looking for could come from the right and left singular vectors of $C$, but I don't know how to compute these singular vectors based on $A^{\top} A$, $B^{\top} B$ and $B^{\top} A$. Worst even, even if I had these $U$ and $V$, it is not clear how to compute $UA$ and $VB$ without explicitly representing $A$ and $B$.

EDIT 2: I think I managed to refine the question some more:

Assume we have the matrix equation:

$(U^{\top} A) (Q \Lambda Q^{\top}) (A^{\top} U) = \Sigma$

such that all matrices in this equation have real values and ($d > n$):

$U$ is $d \times d$ and is orthonormal

$A$ is $d \times n$

$Q$ is $n \times n$ and is orthonormal

$\Lambda$ is $n \times n$ and is diagonal (with only non-negative values)

$\Sigma$ is $d \times d$ and is diagonal (with only non-negative values)

Is there a way to extract the matrix $U^{\top} A$ if we know: $\Sigma$, $\Lambda$ and $Q$ but don't know $A$, $U$? (I think this can be phrased more "mathematically" as a question about a uniqueness of a solution, but not sure how.)

I wouldn't mind getting $U^{\top} A$ up to an invertible linear transformation, as long as this transformation is a function of $U$ only. What if $A$ contains $n$ orthonormal vectors of length $d$? I think this has an easier solution.


1 Answer 1


I don't think that there is an easy relation. The reason behind my thinking is that even for the following "nice" case, we have only a weak relation.

Let $A$ and $B$ be matrices for which the product $AB^T$ is normal (i.e., $BA^TAB^T = AB^TBA^T$). Then,

$$\sigma(AB^T)\quad \prec_w\quad \sigma(B^TA),$$

where $\prec_w$ denotes the weak majorization relation, and $\sigma(\cdot)$ denotes the vector of singular values sorted in descending order.

  • $\begingroup$ thanks. I think my preliminary question here is much too general than it needs to be, which is why it has no satisfying answer. I added a refinement for the question. $\endgroup$
    – kloop
    Feb 1, 2012 at 5:31

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.