Given Gaussian "noise" matrix $G$ and matrix products $AG$, and $A^\intercal AG$, solve for $A$
Let $A \in \mathbb{R}^{m \times n}$ be a matrix with rank $k$. Consider the following randomized procedure:
- Draw a matrix $G \in \mathbb{R}^{n \times k}$ with i.i.d $N(0,1)$ Gaussian entries.
- Form the matrix $Y = AG \in \mathbb{R}^{m \times k}$
- Form the matrix $Z = A^\intercal Y \in \mathbb{R}^{n \times k}$
Is it possible to reconstruct $A$ and its singular value decomposition from the information provided by the matrices $(G,Y,Z)$? If yes, then specify an algorithm. If no, then provide a counterexample.
My work:
We are trying to solve for $A$ given $G,AG,A^\intercal AG$.
For vector $\vec{v}$ in inner product space $X$, use the notation $(\vec{v})^*: X \to \mathbb{R}$, $\vec{x} \mapsto = {\langle \vec{v}, \vec{x} \rangle}$.
SVD decompositions:
\begin{gather*} A = \sum\limits_{i=1}^k \vec{u}_{A,i} \sigma_{A,i} (\vec{v})^*_{A,i}, \quad A^\intercal = \sum\limits_{i=1}^k \vec{v}_{A,i} \sigma_{A,i} (\vec{u})^*_{A,i}, \quad G = \sum\limits_{t=1}^k \vec{u}_{G,t} \sigma_{G,t} (\vec{v})^*_{G,t} \\ \vec{u}_{A,i} \in \mathbb{R}^m, \; \vec{v}_{A,i} \in \mathbb{R}^n, \quad \vec{u}_{G,i} \in \mathbb{R}^n, \; \vec{v}_{G,i} \in \mathbb{R}^k \\ \end{gather*}
\begin{align*} A^\intercal A &= \sum\limits_{i=1}^k (\vec{v}_{A,i} \sigma_{A,i} (\vec{u})^*_{A,i}) \sum\limits_{j=1}^k (\vec{u}_{A,j} \sigma_{A,j} (\vec{v})^*_{A,j}) = \sum\limits_{i=1}^k \vec{v}_{A,i} \sigma_{A,i}^2 (\vec{v})^*_{A,i} \\ AG &= \sum\limits_{i=1}^k (\vec{u}_{A,i} \sigma_{A,i} (\vec{v})^*_{A,i}) \sum\limits_{t=1}^k (\vec{u}_{G,t} \sigma_{G,t} (\vec{v})^*_{G,t}) = \sum\limits_{i=1}^k \sum\limits_{t=1}^k \vec{u}_{A,i} \sigma_{A,i} {\langle \vec{v}_{A,i}, \vec{u}_{G,t} \rangle} \sigma_{G,t} (\vec{v})^*_{G,t} \\ A^\intercal AG &= \sum\limits_{i=1}^k (\vec{v}_{A,i} \sigma_{A,i}^2 (\vec{v})^*_{A,i}) \sum\limits_{t=1}^k (\vec{u}_{G,t} \sigma_{G,t} \vec{v}^*_{G,t}) = \sum\limits_{i=1}^k \sum\limits_{t=1}^k \vec{v}_{A,i} \sigma_{A,i}^2 {\langle \vec{v}_{A,i}, \vec{u}_{G,t} \rangle} \sigma_{G,t} (\vec{v})^*_{G,t} \\ \end{align*}
We have two systems of equations:
\begin{align*} \sum\limits_{r=1}^k \vec{u}_{AG,r} \sigma_{AG,r} (\vec{v})^*_{AG,r} &= \sum\limits_{i=1}^k \sum\limits_{t=1}^k \vec{u}_{A,i} \sigma_{A,i} {\langle \vec{v}_{A,i}, \vec{u}_{G,t} \rangle} \sigma_{G,t} (\vec{v})^*_{G,t} \\ \sum\limits_{s=1}^k \vec{u}_{A^\intercal AG,s} \sigma_{A^\intercal AG,s} (\vec{v})^*_{A^\intercal AG,s} &= \sum\limits_{i=1}^k \sum\limits_{t=1}^k \vec{v}_{A,i} \sigma_{A,i}^2 {\langle \vec{v}_{A,i}, \vec{u}_{G,t} \rangle} \sigma_{G,t} (\vec{v})^*_{G,t} \\ \end{align*}
This looks like it can be solved but I'm not sure how to proceed from here.