Randomized Numerical Linear Algebra for Large Scale Data Analysis Publications



2014

Provable Deterministic Leverage Score Sampling
Dimitris Papailiopoulos, Anastasios Kyrillidis, Christos Boutsidis
Technical Report, 2014

Random Laplace Feature Maps for Semigroup Kernels on Histograms
Jiyan Yang, Vikas Sindhwani, Quanfu Fan, Haim Avron, Michael Mahoney
IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2014

Efficient Dimensionality Reduction for Canonical Correlation Analysis
Haim Avron, Christos Boutsidis, Sivan Toledo, Anastasios Zouzias
SIAM Journal on Scientific Computing 36(5), S111-S131, 2014
Preliminary version appeared in the Proceedings of the 30th International Conference on Machine Learning (ICML), 2013

Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels
Jiyan Yang*, Vikas Sindhwani*, Haim Avron*, Michael Mahoney
Proceedings of the 31th International Conference on Machine Learning (ICML), 2014
(*) Equal contributors.

Kernel Methods Match Deep Neural Networks on TIMIT
Po-Sen Huang, Haim Avron, Tara Sainath, Vikas Sindhwani, Bhuvana Ramabhadran
IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2014
Best Student Paper Award

Optimal CUR Matrix Decompositions
Christos Boutsidis, David Woodruff
ACM Symposium on Theory of Computing (STOC), 2014

Efficient Dimensionality Reduction for Canonical Correlation Analysis
Haim Avron, Christos Boutsidis, Sivan Toledo, Anastasios Zouzias
SIAM Journal on Scientific Computing, to appear 36(5), S111--S131, SIAM, 2014

Faster SVD-truncated Regularized Least-squares
Christos Boutsidis, Malik Magdon-Ismail
Technical Report, 2014

A Note on Sparse Least-squares Regression
C. Boutsidis and M. Magdon-Ismail
Information Processing Letters, to appear, 2014

Approximate Spectral Clustering via Randomized Sketching
A. Gittens, A. Kambadur, C. Boutsidis.
Technical Report, updated Feb 15, 2014

Revisiting Asynchronous Linear Solvers: Provable Convergence Rate Through Randomization
Haim Avron, Alex Druinsky, Anshul Gupta
Proceeding of the 28th IEEE International Parallel & Distributed Processing Symposium (IPDPS) , 2014

Random Projections for Linear Support Vector Machines
S. Paul, C. Boutsidis, M. Magdon-Ismail, P. Drineas
ACM Transactions on Knowledge Discovery from Data, to appear, 2014


2013

Large Scale Subgraph Node Centrality Computations
Yves Ineichen, Costas Bekas, Alessandro Curioni
Technical Report, 2013
Abstract

Highly Scalable Linear Time Estimation of Spectrograms - A Tool for Very Large Scale Data Analysis
O. Bhardwaj, Y. Ineichen, C. Bekas, and A. Curioni
SC 13, 2013
Abstract


Low rank approximation and regression in input sparsity time
Kenneth L Clarkson, David P Woodruff
Proceedings of the 45th annual ACM symposium on theory of computing, pp. 81--90, 2013
http://arxiv.org/abs/1207.6365

Randomized Dimensionality Reduction for K-means Clustering
C. Boutsidis, A. Zouzias, M.W. Mahoney, and P. Drineas
arXiv preprint arXiv:1110.2897, 2013

Deterministic Feature Selection for K-means Clustering
C. Boutsidis, M. Magdon-Ismail
IEEE Transactions on Information Theory, 59(9), 6099 - 6110, 2013

Near-optimal Coresets For Least-Squares Regression
C. Boutsidis, P. Drineas, M. Magdon-Ismail
IEEE Transactions on Information Theory, 59(10), 6880 - 6892, 2013

Improved matrix algorithms via the Subsampled Randomized Hadamard Transform
C. Boutsidis, A. Gittens
SIAM Journal on Matrix Analysis and Applications, 34(3), 1301-1340, 2013

Random Projections for Support Vector Machines
S. Paul, C. Boutsidis, M. Magdon-Ismail, P. Drineas
International Conference on Artificial Intelligence and Statistics (AISTATS), 2013

Near-Optimal Column-Based Matrix Reconstruction
C. Boutsidis, P. Drineas, and M. Magdon-Ismail
SIAM Journal on Computing, special issue of FOCS 2011, 2013

Faster Subset Selection for Matrices and Applications
Haim Avron, Christos Boutsidis
SIAM Journal on Matrix Analysis and Applications 34(4), 2013
Also available on arxiv: http://arxiv.org/abs/1201.0127

Efficient Dimensionality Reduction for Canonical Correlation Analysis
H. Avron, C. Boutsidis, S. Toledo, A. Zouzias
Proceedings of the 30th International Conference on Machine Learning (ICML), 2013

Spectral Condition-Number Estimation of Large Sparse Matrices
H. Avron, A. Druinsky, S. Toledo
CoRRabs/1301.1107, 2013

Sketching Structured Matrices for Faster Nonlinear Regression
Haim Avron, Vikas Sindhwani, David Woodruff
Advances in Neural Information Processing Systems (NIPS), 2013


2012

Efficient and Practical Stochastic Subgradient Descent for Nuclear Norm Regularization
Haim Avron, Satyen Kale, Shiva Kasiviswanathan, Vikas Sindhwani
Proceedings of the 29th International Conference on Machine Learning (ICML), 2012
Extended version appeared as an IBM Research Report (http://domino.research.ibm.com/library/cyberdig.nsf/papers/B6A6347CBFD55F4285257A1300500242)

The fast Cauchy transform: with applications to basis construction, regression, and subspace approximation in l1
Kenneth L Clarkson, Petros Drineas, Malik Magdon-Ismail, Michael W Mahoney, Xiangrui Meng, David P Woodruff
arXiv preprint arXiv:1207.4684, 2012


2011


Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix
Haim Avron, Sivan Toledo
J. ACM 58(8), 1-34, ACM, 2011
Abstract

Topics in Matrix Sampling Algorithms
C. Boutsidis
Ph.D Dissertation, Rensselaer Polytechnic Institute , 2011

Sparse Features for PCA-like Linear Regression
C. Boutsidis, P. Drineas, and M. Magdon-Ismail
Annual Conference on Neural Information Processing Systems (NIPS), 2011

Near-Optimal Column-Based Matrix Reconstruction
C. Boutsidis, P. Drineas, and M. Magdon-Ismail
Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2011

Subspace embeddings for the L 1-norm with applications
Christian Sohler, David P Woodruff
Proceedings of the 43rd annual ACM symposium on Theory of computing, pp. 755--764, 2011

Fast approximation of matrix coherence and statistical leverage
Petros Drineas, Malik Magdon-Ismail, Michael W Mahoney, David P Woodruff
arXiv preprint arXiv:1109.3843, 2011


2010

Blendenpik: Supercharging LAPACK's Least-Squares Solver
Haim Avron, Petar Maymounkov, Sivan Toledo
SIAM Journal on Scientific Computing 32(3), 1217-1236, SIAM, 2010

Random Projections for K-means Clustering
C. Boutsidis, A. Zouzias, and P. Drineas
Annual Conference on Neural Information Processing Systems (NIPS), 2010

Coresets and sketches for high dimensional subspace approximation problems
Dan Feldman, Morteza Monemizadeh, Christian Sohler, David P Woodruff
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 630--649, 2010


2009

An Improved Approximation Algorithm for the Column Subset Selection Problem
C. Boutsidis, M.W. Mahoney, and P. Drineas
ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009

Unsupervised Feature Selection for the K-means Clustering Problem
C. Boutsidis, M.W. Mahoney, and P. Drineas
Annual Conference on Neural Information Processing Systems (NIPS), 2009

Random Projections for the Nonnegative Least Squares Problem
C. Boutsidis, P. Drineas
Linear Algebra and its Applications, Volume 431, Issues 5-7, 1 August 2009, pages 760-771.

Numerical linear algebra in the streaming model
Kenneth L Clarkson, David P Woodruff
Proceedings of the 41st annual ACM symposium on Theory of computing, pp. 205--214, 2009


2008

Unsupervised Feature Selection for Principal Components Analysis
C. Boutsidis, M.W. Mahoney, and P. Drineas
ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2008


Year Unknown

On Sketching Matrix Norms and the Top Singular Vector
Yi Li, Huy L Nguy\^en, David P Woodruff
researcher.ibm.com, 0