81 citations · 340 across the 21 of their papers we have counts for
17 papers · 1 filter
Optimal Principal Component Analysis in Distributed and Streaming Models
Christos Boutsidis, David P. Woodruff, Peilin Zhong
We study the Principal Component Analysis (PCA) problem in the distributed and streaming models of computation. Given a matrix a rank parameter $k < rank(A)…
A Randomized Algorithm for Approximating the Log Determinant of a Symmetric Positive Definite Matrix
Christos Boutsidis, Petros Drineas, Prabhanjan Kambadur +2
We introduce a novel algorithm for approximating the logarithm of the determinant of a symmetric positive definite (SPD) matrix. The algorithm is randomized and approximates the tr…
Greedy Minimization of Weakly Supermodular Set Functions
Christos Boutsidis, Edo Liberty, Maxim Sviridenko
This paper defines weak--supermodularity for set functions. Many optimization objectives in machine learning and data mining seek to minimize such functions under cardinality co…
Optimal CUR Matrix Decompositions
Christos Boutsidis, David P. Woodruff
The CUR decomposition of an matrix finds an matrix with a subset of columns of together with an matrix with a subset…
Provable Deterministic Leverage Score Sampling
Dimitris Papailiopoulos, Anastasios Kyrillidis, Christos Boutsidis
We explain theoretically a curious empirical phenomenon: "Approximating a matrix by deterministically selecting a subset of its columns with the corresponding largest leverage scor…
Faster SVD-Truncated Least-Squares Regression
Christos Boutsidis, Malik Magdon-Ismail
We develop a fast algorithm for computing the "SVD-truncated" regularized solution to the least-squares problem: $ \min_{\x} \TNorm{\matA \x - \b}. $ Let $\matA_k$ of rank be t…