Low-Rank Approximations with Sparse Factors I: Basic Algorithms and Error Analysis

SIAM Journal on Matrix Analysis and ApplicationsPublished 1 January 2002

Zhenyue Zhang, Hongyuan Zha, Horst D. Simon

DOI10.1137/s0895479899359631

Source URL

Citations76

SJR quartileQ1

SJR score0.92

SNIP1.34

TL;DR

This work considers the problem of computing low-rank approximations of matrices in a factorized form with sparse factors and presents numerical examples arising from some application areas to illustrate the efficiency and accuracy of the proposed algorithms.

Abstract

We consider the problem of computing low-rank approximations of matrices. The novel aspects of our approach are that we require the low-rank approximations to be written in a factorized form with sparse factors, and the degree of sparsity of the factors can be traded off for reduced reconstruction error by certain user-determined parameters. We give a detailed error analysis of our proposed algorithms and compare the computed sparse low-rank approximations with those obtained from singular value decomposition. We present numerical examples arising from some application areas to illustrate the efficiency and accuracy of our algorithms.

Keywords

Computer ScienceMathematicsEngineering

NatureLearning the parts of objects by non-negative matrix factorization

14,055 Citations1999Daniel D. Lee, H. Sebastian Seung

An algorithm for non-negative matrix factorization is demonstrated that is able to learn parts of faces and semantic features of text and is in contrast to other methods that learn holistic, not parts-based, representations.

SIAM Journal on ComputingSparse Approximate Solutions to Linear Systems

2,822 Citations1995B. K. Natarajan

It is shown that the problem is NP-hard, but that the well-known greedy heuristic is good in that it computes a solution with at most at most $\left\lceil 18 \mbox{ Opt} ({\bf \epsilon}/2) \|{\bf A}^+\|^2_2 \ln(\|b\|_2/{\bf

SIAM ReviewUsing Linear Algebra for Intelligent Information Retrieval

1,484 Citations1995Michael W. Berry, Susan Dumais +1 more

A lexical match between words in users’ requests and those in or assigned to documents in a database helps retrieve textual materials from scientific databases.

Applied mathematical sciencesMatrix Perturbation Theory

1,398 Citations1991V. N. Bogaevski, А. А. Повзнер

X is the vector space which acts in the n-dimensional (complex) vector space R.1.1 and is related to Varepsilon by the following inequality.

ACM Transactions on Information SystemsA semidiscrete matrix decomposition for latent semantic indexing information retrieval

224 Citations1998Tamara G. Kolda, Dianne P. O’Leary

It is shown that SDD- based LSI does as well as SVD-based LSI in terms of document retrieval while requiring only one-twentieth the storage and one-half the time to compute each query.

View PDF

SIAM Journal on Scientific ComputingLow-Rank Matrix Approximation Using the Lanczos Bidiagonalization Process with Applications

145 Citations2000Horst D. Simon, Hongyuan Zha

It is demonstrated that a so-called one-sided reorthogonalization process can be used to maintain an adequate level of orthogonality among the Lanczos vectors and produce accurate low-rank approximations.

Numerische MathematikFour algorithms for the the efficient computation of truncated pivoted QR approximations to a sparse matrix

133 Citations1999G. W. Stewart

Four algorithms to compute truncated pivoted pivoted QR approximations to a sparse matrix based on the Gram–Schmidt algorithm and the other on Householder triangularization are proposed.

SIAM Journal on Matrix Analysis and ApplicationsOn the Optimality of the Backward Greedy Algorithm for the Subset Selection Problem

114 Citations2000Christophe Couvreur, Yoram Bresler

The backward greedy algorithm is shown to be optimal for the subset selection problem in the sense that it selects the "correct" subset of columns from A if the perturbation of the data vector b is small enough.

IRE Transactions on Communications SystemsDigital Image Compression by Outer Product Expansion

78 Citations1983Dianne P. O’Leary, Bezalel Peleg

A digital image is approximate as a sum of outer products dxyT where d is a real number but the vectors x and y have elements +1, -1, or 0 only and the expansion gives a least squares approximation.

BIT Numerical MathematicsLow Rank Approximation of a Hankel Matrix by Structured Total Least Norm

63 Citations1999H. Park, L. Zhang +1 more

A new method is presented for structure preserving low rank approximation of a matrix, which is based on Structured Total Least Norm (STLN), an efficient method for obtaining an approximate solution to an overdetermined linear system.