Fetching the paper…
Reading the bibliography…
We study the $\ell_1$-low rank approximation problem, where for a given $n \times d$ matrix $A$ and approximation factor $\alpha \geq 1$, the goal is to output a rank-$k$ matrix $\widehat{A}$ for which $$\|A-\widehat{A}\|_1 \leq \alpha \cdot \min_{\textrm{rank-}k\textrm{ matrices}~A'}\|A-A'\|_1,$$ where for an $n \times d$ matrix $C$, we let $\|C\|_1 = \sum_{i=1}^n \sum_{j=1}^d |C_{i,j}|$.
Information and information stability of random variables and processes
Mark S Pinsker · 1960
Earlier work this paper cites.
Gaussian elimination is not optimal
Volker Strassen · 1969
Earlier work this paper cites.
Probabilistic computations: Toward a unified measure of complexity
Andrew Chi-Chin Yao · 1977
Earlier work this paper cites.
Matrix multiplication via arithmetic progressions
Don Coppersmith and Shmuel Winograd · 1987
Earlier work this paper cites.
On the computational complexity and geometry of the first-order theory of the reals, part I: introduction. preliminaries. the geometry of semi-algebraic sets. the decision problem for the existential theory of the reals
James Renegar · 1992
Earlier work this paper cites.
On the computational complexity and geometry of the first-order theory of the reals, part II: the general decision problem. preliminaries for quantifier elimination
James Renegar · 1992
Earlier work this paper cites.
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
Michel X Goemans and David P Williamson · 1995
Earlier work this paper cites.
On the combinatorial and algebraic complexity of quantifier elimination
Saugata Basu, Richard Pollack, and Marie-Françoise Roy · 1996
Earlier work this paper cites.
Free bits, pcps, and nonapproximability—towards tight results
Mihir Bellare, Oded Goldreich, and Madhu Sudan · 1998
Earlier work this paper cites.
Which problems have strongly exponential complexity?
Russell Impagliazzo, Ramamohan Paturi, and Francis Zane · 1998
Earlier work this paper cites.
A parallel divide and conquer algorithm for the symmetric eigenvalue problem on distributed memory architectures
Françoise Tisseur and Jack Dongarra · 1999
Earlier work this paper cites.
Gadgets, approximation, and linear programming
Luca Trevisan, Gregory B Sorkin, Madhu Sudan, and David P Williamson · 2000
Earlier work this paper cites.
Some optimal inapproximability results
Johan Håstad · 2001
Earlier work this paper cites.
Detection, estimation, and modulation theory
H. L. Van Trees · 2001
Earlier work this paper cites.
Principal component analysis for dimension reduction in massive distributed data sets
Yongming Qu, George Ostrouchov, Nagiza Samatova, and Al Geist · 2002
Earlier work this paper cites.
Fast image retrieval via embeddings
Piotr Indyk and Nitin Thaper · 2003
Earlier work this paper cites.
Robust subspace computation using ℓ 1 \ell_{1} norm
Qifa Ke and Takeo Kanade · 2003
Earlier work this paper cites.
Principal component analysis for distributed data sets with updating
Zheng-Jian Bai, Raymond H Chan, and Franklin T Luk · 2005
Earlier work this paper cites.
Algorithms in real algebraic geometry
Saugata Basu, Richard Pollack, and Marie-Francoise Roy · 2005
Earlier work this paper cites.
Subgradient and sampling algorithms for ℓ 1 \ell_{1} regression
Kenneth L Clarkson · 2005
Earlier work this paper cites.
Robust ℓ 1 \ell_{1} norm factorization in the presence of outliers and missing data by alternative convex programming
Qifa Ke and Takeo Kanade · 2005
Earlier work this paper cites.
Data Streams: Algorithms and Applications
S. Muthukrishnan · 2005
Earlier work this paper cites.
Subspace sampling and relative-error matrix approximation: Column-based methods
Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan · 2006
Earlier work this paper cites.
Subspace sampling and relative-error matrix approximation: Column-row-based methods
Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan · 2006
Earlier work this paper cites.
R1-pca: rotational invariant ℓ 1 \ell_{1} -norm principal component analysis for robust subspace factorization
Chris Ding, Ding Zhou, Xiaofeng He, and Hongyuan Zha · 2006
Earlier work this paper cites.
Stable distributions, pseudorandom generators, embeddings, and data stream computation
Piotr Indyk · 2006
Earlier work this paper cites.
Open problems in data streams and related topics
Andrew McGregor · 2006
Earlier work this paper cites.
Improved approximation algorithms for large matrices via random projections
Tamás Sarlós · 2006
Earlier work this paper cites.
Sampling-based dimension reduction for subspace approximation
Amit Deshpande and Kasturi R. Varadarajan · 2007
Earlier work this paper cites.
Generalized rank-constrained matrix approximations
Shmuel Friedland and Anatoli Torokhti · 2007
Earlier work this paper cites.
Optimal inapproximability results for max-cut and other 2-variable csps?
Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell · 2007
Earlier work this paper cites.
Earth mover distance over high-dimensional spaces
Alexandr Andoni, Piotr Indyk, and Robert Krauthgamer · 2008
Earlier work this paper cites.
Distributed principal component analysis for wireless sensor networks
Yann-Ael Le Borgne, Sylvain Raybaud, and Gianluca Bontempi · 2008
Earlier work this paper cites.
Relative-error CUR matrix decompositions
Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan · 2008
Earlier work this paper cites.
Robust ℓ 1 \ell_{1} principal component analysis and its bayesian variational inference
Junbin Gao · 2008
Earlier work this paper cites.
Practical global optimization for multiview geometry
Fredrik Kahl, Sameer Agarwal, Manmohan Krishna Chandraker, David Kriegman, and Serge Belongie · 2008
Earlier work this paper cites.
Principal component analysis based on ℓ 1 \ell_{1} -norm maximization
Nojun Kwak · 2008
Earlier work this paper cites.
The matrix cookbook
Kaare Brandt Petersen, Michael Syskind Pedersen, et al · 2008
Earlier work this paper cites.
Computational complexity: a modern approach
Sanjeev Arora and Boaz Barak · 2009
Earlier work this paper cites.
Efficient sketches for earth-mover distance, with applications
Alexandr Andoni, Khanh Do Ba, Piotr Indyk, and David P Woodruff · 2009
Cited alongside, same era.
An improved approximation algorithm for the column subset selection problem
Christos Boutsidis, Michael W Mahoney, and Petros Drineas · 2009
Cited alongside, same era.
Numerical linear algebra in the streaming model
Kenneth L. Clarkson and David P. Woodruff · 2009
Cited alongside, same era.
Sampling algorithms and coresets for ℓ p \ell_{p} regression
Anirban Dasgupta, Petros Drineas, Boulos Harb, Ravi Kumar, and Michael W Mahoney · 2009
Cited alongside, same era.
Spectral algorithms
Ravi Kannan and Santosh Vempala · 2009
Cited alongside, same era.
Markov chains and mixing times
David Asher Levin, Yuval Peres, and Elizabeth Lee Wilmer · 2009
Cited alongside, same era.
A cyclic weighted median method for ℓ 1 \ell_{1} low-rank matrix factorization with missing entries
Deyu Meng, Zongben Xu, Lei Zhang, and Ji Zhao · 2013
Later among the works it cites.
Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings
Jelani Nelson and Huy L Nguyên · 2013
Later among the works it cites.
Elemental: A new framework for distributed memory dense matrix computations
Jack Poulson, Bryan Marker, Robert A van de Geijn, Jeff R Hammond, and Nichols A Romero · 2013
Later among the works it cites.
Subspace embeddings and ℓ p \ell_{p} -regression using exponential random variables
David P. Woodruff and Qin Zhang · 2013
Later among the works it cites.
Algorithms in real algebraic geometry: a survey
Saugata Basu · 2014
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Nonnegative matrix factorization with earth mover’s distance metric
Roman Sandler and Michael Lindenbaum · 2009
Cited alongside, same era.
Introduction to nonparametric estimation. revised and extended from the 2004 french original. translated by vladimir zaiats, 2009
Alexandre B Tsybakov · 2009
Cited alongside, same era.
Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization
John Wright, Arvind Ganesh, Shankar Rao, Yigang Peng, and Yi Ma · 2009
Cited alongside, same era.
Efficient volume sampling for row/column subset selection
Amit Deshpande and Luis Rademacher · 2010
Cited alongside, same era.
Coresets and sketches for high dimensional subspace approximation problems
Dan Feldman, Morteza Monemizadeh, Christian Sohler, and David P. Woodruff · 2010
Cited alongside, same era.
On the exact space complexity of sketching and streaming small norms
Daniel M Kane, Jelani Nelson, and David P Woodruff · 2010
Cited alongside, same era.
Improved distributed principal component analysis
Maria-Florina Balcan, Vandana Kanchanapally, Yingyu Liang, and David Woodruff · 2014
Later among the works it cites.
Optimal cur matrix decompositions
Christos Boutsidis and David P Woodruff · 2014
Later among the works it cites.
Single pass spectral sparsification in dynamic streams
Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, and Aaron Sidford · 2014
Later among the works it cites.
Principal component analysis and higher correlations for distributed data
Ravindran Kannan, Santosh S Vempala, and David P Woodruff · 2014
Later among the works it cites.
Optimal algorithms for ℓ 1 \ell_{1} -subspace signal processing
Panos P. Markopoulos, George N. Karystinos, and Dimitrios A. Pados · 2014
Later among the works it cites.
Lower bounds for oblivious subspace embeddings
Jelani Nelson and Huy L Nguyên · 2014
Later among the works it cites.
Non-convex robust pca
Praneeth Netrapalli, UN Niranjan, Sujay Sanghavi, Animashree Anandkumar, and Prateek Jain · 2014
Later among the works it cites.
Optimal mean robust principal component analysis
Feiping Nie, Jianjun Yuan, and Heng Huang · 2014
Later among the works it cites.
Total variation distance and the distribution of relative information
Sergio Verdú · 2014
Later among the works it cites.
Low rank approximation lower bounds in row-update streams
David P Woodruff · 2014
Later among the works it cites.
Sketching as a tool for numerical linear algebra
David P. Woodruff · 2014
Later among the works it cites.
Toward a unified theory of sparse dimensionality reduction in euclidean space
Jean Bourgain, Sjoerd Dirksen, and Jelani Nelson · 2015
Later among the works it cites.
Uniform sampling for matrix approximation
Michael B Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford · 2015
Later among the works it cites.
ℓ p \ell_{p} row sampling by lewis weights
Michael B. Cohen and Richard Peng · 2015
Later among the works it cites.
Input sparsity and hardness for robust subspace approximation
Kenneth L Clarkson and David P Woodruff · 2015
Later among the works it cites.
Sketching for m-estimators: A unified approach to robust regression
Kenneth L Clarkson and David P Woodruff · 2015
Later among the works it cites.
Sub-exponential approximation schemes for csps: From dense to almost sparse
Dimitris Fotakis, Michael Lampis, and Vangelis Th Paschos · 2015
Later among the works it cites.
On the complexity of robust pca and e l l _ 1 ell\_1 -norm low-rank matrix approximation
Nicolas Gillis and Stephen A Vavasis · 2015
Later among the works it cites.
Efficient-norm-based low-rank matrix approximations for large-scale problems using alternating rectified gradient method
Eunwoo Kim, Minsik Lee, Chong-Ho Choi, Nojun Kwak, and Songhwai Oh · 2015
Later among the works it cites.
Analysis of robust pca via local incoherence
Huishuai Zhang, Yi Zhou, and Yingbin Liang · 2015
Later among the works it cites.
Computing approximate PSD factorizations
Amitabh Basu, Michael Dinitz, and Xin Li · 2016
Closest in time.
Nearly-optimal bounds for sparse recovery in generic norms, with applications to k-median sketching
Arturs Backurs, Piotr Indyk, Ilya Razenshteyn, and David P Woodruff · 2016
Closest in time.
Distributed kernel principal component analysis
Maria-Florina Balcan, Yingyu Liang, Le Song, David Woodruff, and Bo Xie · 2016
Closest in time.
Optimal principal component analysis in distributed and streaming models
Christos Boutsidis, David P Woodruff, and Peilin Zhong · 2016
Closest in time.
On robust low-rank approximation
Flavio Chierichetti, Sreenivas Gollapudi, Ravi Kumar, Silvio Lattanzi, and Rina Panigrahy · 2016
Closest in time.
Robust principal component analysis with side information
Kai-Yang Chiang, Cho-Jui Hsieh, and Inderjit S Dhillon · 2016
Closest in time.
Nearly tight oblivious subspace embeddings by trace inequalities
Michael B. Cohen · 2016
Closest in time.
Wuchen Li, Stanley Osher, and Wilfrid Gangbo · 2016
Closest in time.
Efficient ℓ 1 \ell_{1} -Norm Principal-Component Analysis via Bit Flipping
P. P. Markopoulos, S. Kundu, S. Chamadia, and D. A. Pados · 2016
Closest in time.
Iteratively reweighted least squares algorithms for ℓ 1 \ell_{1} -norm principal component analysis
Young Woong Park and Diego Klabjan · 2016
Closest in time.
Fast regression with an ℓ ∞ {\ell}_{\infty} guarantee
Eric Price, Zhao Song, and David P. Woodruff · 2016
Closest in time.
Weighted low rank approximations with provable guarantees
Ilya Razenshteyn, Zhao Song, and David P Woodruff · 2016
Closest in time.
Distributed low rank approximation of implicit functions of a matrix
David P Woodruff and Peilin Zhong · 2016
Closest in time.