Matrix factorization for dimensional reduction similar to spectral decomposition/SVD I have a graph clustering problem I'm working on and it basically involves finding a factorization of the adjacency matrix $A$ such that the following equations are (approximately) satisfied:
$$
A \approx L \tilde{A} R,\quad
RL\approx \mathbb{I}_k \\
A \in \mathbb{R}^{n \times n},\;
L \in \mathbb{R}^{n \times k},\;
R \in \mathbb{R}^{k \times n},\;
\tilde{A} \in \mathbb{R}^{k \times k},\;
\text{and}\; k < n
$$
where $A$ and $k$ are inputs, and I would like to calculate $L$, $\tilde{A}$, and $R$. On the face of things, this seems like it's just begging for a spectral or singular value decomposition, but the problem is that $A$ and $\tilde{A}$ have different sizes. I could just do a spectral decomposition and throw away the eigenvectors with the smallest eigenvalues, but (1) if the eigenvalues are all roughly the same magnitude it could introduce large error, and (2) I would actually prefer if $\tilde{A}$ was NOT diagonal, because it has an interpretation as a coarsened/clustered version of the original adjacency matrix, and diagonal adjacency matrices are not interesting to me.
I'm hoping this is a problem that has already been solved, so I don't have to reinvent the wheel here. I tried looking for an algorithm (ideally in the form of a python package) to compute this factorization but haven't been able to find anything. I assume that since there is some dimensional reduction involved this is not exactly soluble and an approximate solution that minimizes some norm $||A - L \tilde{A} R||$ would be satisfactory. Does anyone know if a solution for this type of problem already exists? And if not, what might be the most efficient way to solve it? Gradient descent? Some generalization of ALS?
 A: *

*I would suggest you to attach no particular meaning to $\tilde{A}$ being diagonal, because you have enough freedom to introduce changes of basis there: for any invertible $M$, you can replace $L,\tilde{A},R$ with  $LM$, $M^{-1}\tilde{A}M$ and $M^{-1}R$. So $\tilde{A}$ can always be made diagonal, or at least in Jordan form.

*The drawback you point out with SVD (poor approximation if the singular values all have the same magnitude) is actually intrinsic of any type of low-rank approximation: no matter which low-rank approximation $A\approx MN$, $M,N^T\in\mathbb{R}^{n\times k}$ you compute, you can't beat SVD because its error in the Euclidean spectral norm is bounded by $\|A-MN\| \geq \sigma_{k+1}$ (Eckart-Young-Mirsky theorem).

*That said, I don't see any possibilities for improvement with respect to just using truncated SVD. $A \approx U_k S_k V_k^T = U_k (S_k V_k^TU_k) U_k^T$ is the decomposition you are looking for. Or, more precisely, $L = U_kM $, $\tilde{A} = M^{-1}S_k V_k^TU_kM$, $R = M^{-1}U_k^T$, for any invertible $M$ (see point 1). It gives you the best rank-$k$ approximation of $A$ in the Euclidean norm and in the Frobenius norm. 
