Restoring matrix from covariance matrix 
*

*Given $ A^TA $, how to restore $A$?  (Any $A$ which produces this $ A^TA $).

*Given matrix $ A^TA $, vector $b$, and vector $Ab$, how to restore a matrix $A$ ?
Correction to 2: The vector $A^Tb$, not Ab.
 A: 1) Using Singular Value Decomposition, for any $A \in \mathbb{R}^{m \times n}$ we can write $A = USV^T$ where $S \in \mathbb{R}^{r \times r}$ is a diagonal matrix whose entries are the square roots of the $r$ non-zero eigenvalues of $A^TA$ (which are the same as those of $AA^T$), $V \in \mathbb{R}^{n \times r}$ is an orthonormal matrix whose columns are the eigenvectors of $A^TA$ which correspond to non-zero eigenvalues, and $U \in \mathbb{R}^{m \times r}$ is an orthonormal matrix whose columns are the eigenvectors of $AA^T$ which correspond to non-zero eigenvalues. 
If we are given $A^TA \in \mathbb{R}^{n \times n}$ with rank $r$, then performing eigendecomposition on $A^TA$ gives us the matrices $S \in \mathbb{R}^{r \times r}$ and $V \in \mathbb{R}^{n \times r}$ as defined above, but we have no way to get the eigenvectors of $AA^T$. Fortunately, for any $m \ge r$ and any matrix $U \in \mathbb{R}^{m \times r}$ with orthonormal columns, we get that $(USV^T)^T(USV^T) = VSU^TUSV^T = VSSV^T = VS^2V^T$, which is precisely the diagonalized form of the given matrix $A^TA$. So, we can simply pick $m = r$ (to minimize the size of $A$), pick $U = I_r$ (the $r \times r$ identity matrix), and then set $\hat{A} = USV^T$. 
2) If we are given $A^TA \in \mathbb{R}^{n \times n}$, a vector $b \in \mathbb{R}^m$, and a vector $A^Tb \in \mathbb{R}^n$, we can still perform eigendecomposition on $A^TA$ to get the matrices $S \in \mathbb{R}^{r \times r}$ and $V \in \mathbb{R}^{n \times r}$. We also know that $A$ has exactly $m$ rows. So, the problem comes down to finding a matrix $U \in \mathbb{R}^{m \times r}$ with orthonormal columns such that $A^Tb = (USV^T)^Tb = VSU^Tb$, i.e. $U^Tb = S^{-1}V^T(A^Tb)$ where $b \in \mathbb{R}^{m}$ and $S^{-1}V^T(A^Tb) \in \mathbb{R}^{r}$ are known vectors. Unfortunately, I don't know of a way to solve this problem. 
