4
$\begingroup$

Suppose two Gram matrices are given $A, B\in\mathbb{R}^{n\times n}$, such that $$A=XX^T,~~~~~~~~~~~~~B=YY^T,$$ for some $X, Y\in\mathbb{R}^{n\times k}$, $k\ll n$. Also, suppose a Gram matrix based on linear interpolation $X+Y$ is denoted by $C=(X+Y)(X+Y)^T$. I'm aware that $$C=A+B+XY^T+YX^T,$$ but I wonder how I could (approximately) get $C$ by only operating on $A$ and $B$. Clearly, by decomposing to $X$ and $Y$ it is possible, but I'm interested in restricted operation on $A$ and $B$ only. So, could one approximate $XY^T$ and $YX^T$ by $A$ and $B$?

If you know of some academic work exploring the above relation, please post it.

$\endgroup$
  • 2
    $\begingroup$ In general you cannot assume $XY^T=YX^T$ (as your expression for $C$ implies). $\endgroup$ – hardmath May 1 '12 at 14:55
6
$\begingroup$

In the restated problem both $X$ and $Y$ have rank at most $k \ll n$, and the same is true of Gram matrices $A$ and $B$. Also $C=(X+Y)(X+Y)^T$ will have rank at most $k$.

The goal of forming $C$ from $A$ and $B$, even approximately, seems unattainable. To briefly enlarge upon Jack Poulson's example, let $X$ and $Y$ be any two matrices such that:

$$ XX^T = YY^T = \begin{pmatrix} I & 0 \\ 0 & 0 \end{pmatrix} $$

where the given nonzero block $I$ is $k \times k$. Thus $X,Y$ might be of this form:

$$ X = \begin{pmatrix} P \\ 0 \end{pmatrix} $$ $$ Y = \begin{pmatrix} Q \\ 0 \end{pmatrix} $$

where $P,Q$ are $k \times k$ orthogonal matrices.

Taking $Q = I$ for simplicity, we see that:

$$ C = (X+Y)(X+Y)^T = 2 \begin{pmatrix} I+P & 0 \\ 0 & 0 \end{pmatrix} $$

So Jack's point is that the problem is not well-defined without further constraints. Knowing $A = XX^T$ and $B = YY^T$ is insufficient to approximate $C$, as $P$ might be any orthogonal matrix of the right size.

Let me suggest that computing $C$ from $A$ and $B$ might be the wrong goal. After all, storing $A$ rather than $X$ (resp. $B$ than $Y$) takes more space, since $X$ is only $n \times k$, but $A$ would generally be a full $n \times n$.

Ordinarily a programmer would be pleased to store the factors $X$ (resp. $Y$) and to do the fairly easy update $X+Y$ rather than compute and store $C$. Saves time, saves space.

Of course one might fear that further operations done implicitly with $C$ using $X+Y$ are less efficient. This is not so, at least with a wide range of studied numeric applications. Consider for example forming a matrix-vector product $Cv$. With explicitly formed $C$ this takes $n^2$ multiplications (and roughly equal number of adds). Doing the implicit product by associativity $(X+Y)(X+Y)^Tv$ only takes $2kn$ multiplies (resp. adds).

$\endgroup$
  • $\begingroup$ I agree completely. Store and compute with $X$ and $Y$, not $A$ and $B$. $\endgroup$ – Jack Poulson May 2 '12 at 6:23
  • $\begingroup$ @JackPoulson: Rolled back, because while it is true that $C$ has rank at most $2k$ (and at first that's what I wrote), in this case $C = (X+Y)(X+Y)^T$ and has rank no more than the factor $X+Y$ does. But $X+Y$ is again $n \times k$, so has rank at most $k$, etc. $\endgroup$ – hardmath May 4 '12 at 4:58
  • $\begingroup$ How is your first sentence not incorrect (i.e., given the statements in his question, $X+K$ could have a rank as high as $2k$)? $\endgroup$ – Jack Poulson May 4 '12 at 7:34
  • $\begingroup$ @JackPoulson: As usero's edited Question has it, both $X,Y$ are $n \times k$ matrices, and so is their sum $X+Y$. So $rank(X+Y)$ is limited by the number of columns it has, $k$. $\endgroup$ – hardmath May 4 '12 at 13:51
  • $\begingroup$ Ah, yes, I am used to thinking about $XX^T + YY^T$, where one forms $[X,Y] [X,Y]^T$, which has a rank of up to $2k$. Very sloppy of me. $\endgroup$ – Jack Poulson May 4 '12 at 15:03
7
$\begingroup$

This problem is not well-defined without constraints on $X$ and $Y$. Consider $X=-I$ and $Y=I$. Then $A=B=I$, but $C=0$.

$\endgroup$
  • $\begingroup$ I've edited my question. I guess it helps the interpretation. $\endgroup$ – usero May 1 '12 at 18:34
  • 2
    $\begingroup$ Your problem is still not well-defined. For any orthogonal $Q$, if $A=XX^T$, then it also holds that $A=(XQ)(XQ)^T$. One possible $Q$ is $-I$. The point is that $X$ and $Y$ are not determined by $A$ and $B$, and so $X+Y$ is certainly not well-determined. $\endgroup$ – Jack Poulson May 1 '12 at 18:48

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.