2010 · 201 citations · 16 references
ComputingComputer ScienceAlgorithmsComputer VisionOptimizationApproximation AlgorithmsMatrix ComputationMatrix FactorizationNumerical AlgorithmsNumerical Linear AlgebraOutlier HandlingLow-rank ApproximationLow-rank Matrix FactorizationLow-rank OptimizationRobust Matrix FactorizationSingular Value DecompositionSparse Matrix AlgorithmsSparse Matrix Computation
The calculation of a low-rank approximation of a matrix is a fundamental operation in many computer vision applications. The workhorse of this class of problems has long been the Singular Value Decomposition. However, in the presence of missing data and outliers this method is not applicable, and unfortunately, this is often the case in practice. In this paper we present a method for calculating the low-rank factorization of a matrix which minimizes the L <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> norm in the presence of missing data. Our approach represents a generalization the Wiberg algorithm of one of the more convincing methods for factorization under the L <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> norm. By utilizing the differentiability of linear programs, we can extend the underlying ideas behind this approach to include this class of L <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> problems as well. We show that the proposed algorithm can be efficiently implemented using existing optimization software. We also provide preliminary experiments on synthetic as well as real world data with very convincing results.
16
Matthew Turk, Alex Pentland · Journal of Cognitive Neuroscience · 1991 · 13.8K citations · Full text
Nonlinear programming: theory and algorithms
Computers & Operations Research · 1993 · 5.8K citations
Linear and nonlinear programming.
Mathematics and Computers in Simulation · 1986 · 4.9K citations
Numerical methods for least squares problems
Choice Reviews Online · 1996 · 3.1K citations