Low-rank approximations with sparse factors. I: Basic algorithms and error analysis (Q2784376)

The problem of computing low-rank approximations of matrices is cast in the framework of an optimization problem. The low-rank approximations are written in a factorized form with sparse factors and the degree of sparsity of the factors is traded off for reduced reconstruction error by certain user defined parameters. Algorithms and heuristics for finding approximate solutions to this optimization problem are proposed.NEWLINENEWLINENEWLINEA detailed error analysis of the proposed algorithms is given and a comparison of the computed sparse low rank approximations with those obtained from singular value decomposition (SVD) is done. Specifically, the authors prove that the reconstruction errors of the computed sparse low-rank approximations are within a constant factor of those that are obtained by SVD.NEWLINENEWLINENEWLINESeveral numerical experiments are conducted to illustrate the various numerical and efficiency issues of the proposed algorithms. Some directions for future research are pointed out.