Recovery of original matrix from a compressed low rank approximation?

Question

Matrix $A$ is compressed by pre and post multiplying with $C^H$ (hermitian transpose of $C$) and $C$ respectively, such that:

$B$ = $C^H$ * $A$ * $C$.

$A$ is $n \times n$, $B$ is $m*m$ and $C$ is $n*m$, where $m << n$. $C$ has orthogonal columns.

Now, I wish to approximate $A$ using B, such that:

$A_{approx}$ $\approx$ $C* B * C^{H}$. However, since $m << n$, the approximation is quite off the original matrix.

Is there any suggestion for a technique to find a matrix $D$ and $E^H$, as in, $A_{approx}$ $\approx$ $D* B * E^{H}$, ensuring minimum $||A - A_{approx}||$?

Answer 1

The best low-rank approximation is given by the Singular Value Decomposition:

$ A = U \Sigma V^H $ where $ U $ and $ V $ are orthogonal (well, unitary since you seem to be working with conjugate transposes) and $ \Sigma $ is diagonal with positive values on the diagonal ordered from largest to smallest.

The best low rank approximation with rank $ r $ is then given by $ A_{approx} = U_L \Sigma_{TL} V_L^H $ where $ U = \left( \begin{array}{c | c} U_L & U_R \end{array} \right) $, $ V = \left( \begin{array}{c | c} V_L & V_R \end{array} \right) $, and $ \Sigma = \left( \begin{array}{c | c} \Sigma_{TL} & 0 \\ 0 & \Sigma_{BR} \end{array} \right) $. Here $ U_L $ and $ V_L $ have $ r $ columns and $ \Sigma_{TL} $ is $ r \times r $.

Answer 2

I don't quite understand your comment "I can't use the SVD".

If you do have the SVD, then you know that $ U_L \Sigma_{TL} V_L^H $ is the best approximation. So, you can then insert $ U_L \Sigma_{TL} B B^{-1} V_L^H $ and then put parentheses in $ ( U_L \Sigma_{TL} ) B ( B^{-1} V_L^H ) $ and, bingo, you have your desired $ D $ and $ E^H $.

I suspect that what you are really saying is that you would like to do this without computing the SVD... That complicates matters.