Structured Variational $D$-Decomposition for Accurate and Stable Low-Rank Approximation
This work addresses matrix approximation for data analysis, offering incremental improvements in accuracy and stability for applications such as recommendation systems and image processing.
The paper tackled the problem of low-rank matrix approximation by introducing the D-decomposition, a non-orthogonal factorization computed via alternating minimization, and demonstrated improved reconstruction accuracy on datasets like MovieLens and MNIST, with specific gains in sparsity and noise conditions.
We introduce the $D$-decomposition, a non-orthogonal matrix factorization of the form $A \approx P D Q$, where $P \in \mathbb{R}^{n \times k}$, $D \in \mathbb{R}^{k \times k}$, and $Q \in \mathbb{R}^{k \times n}$. The decomposition is defined variationally by minimizing a regularized Frobenius loss, allowing control over rank, sparsity, and conditioning. Unlike algebraic factorizations such as LU or SVD, it is computed by alternating minimization. We establish existence and perturbation stability of the solution and show that each update has complexity $\mathcal{O}(n^2k)$. Benchmarks against truncated SVD, CUR, and nonnegative matrix factorization show improved reconstruction accuracy on MovieLens, MNIST, Olivetti Faces, and gene expression matrices, particularly under sparsity and noise.