Component-Wise Squared Factorization

The component-wise squared factorization decomposes a matrix as the component-wise square of a low-rank matrix. It can be used to compute the so-called square root rank of a matrix, used in the compact representation of convex polytopes, but also to represent compactly nonnegative data including arithmetic circuits. This paper introduces a coordinate descent algorithm to solve this problem, along with an accelerated variant using extrapolation. We show that it compresses better dense and sparse nonnegative matrices than standard linear low-rank matrix factorization models such as the truncated singular value decomposition (TSVD) and nonnegative matrix factorization (NMF). Then, we explore its application on synthetic matrices generated for experimentation, and also on the slack matrices of regular n-gons and linear Euclidean distance matrices.