Matrix factorization for dimensional reduction similar to spectral decomposition/SVD

Question

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?

Answer 1

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

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

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