Simplifying some operations on Gram matrices

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.

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

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).

• I agree completely. Store and compute with $X$ and $Y$, not $A$ and $B$. – Jack Poulson May 2 '12 at 6:23
• @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. – hardmath May 4 '12 at 4:58
• 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$)? – Jack Poulson May 4 '12 at 7:34
• @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$. – hardmath May 4 '12 at 13:51
• 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. – Jack Poulson May 4 '12 at 15:03

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$.

• I've edited my question. I guess it helps the interpretation. – usero May 1 '12 at 18:34
• 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. – Jack Poulson May 1 '12 at 18:48