## 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

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

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

Preliminary version appeared in the Proceedings of the 30th International Conference on Machine Learning (ICML), 2013

Haim Avron, Christos Boutsidis, Sivan Toledo, Anastasios Zouzias

*SIAM Journal on Scientific Computing**36*(*5*), S111-S131, 2014Preliminary 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

(*) Equal contributors.

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

Best Student Paper Award

Po-Sen Huang, Haim Avron, Tara Sainath, Vikas Sindhwani, Bhuvana Ramabhadran

*IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP)*, 2014Best Student Paper Award

Optimal CUR Matrix Decompositions

Christos Boutsidis, David Woodruff

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

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

Christos Boutsidis, Malik Magdon-Ismail

Technical Report, 2014

A Note on Sparse Least-squares Regression

C. Boutsidis and M. Magdon-Ismail

C. Boutsidis and M. Magdon-Ismail

*Information Processing Letters, to appear*, 2014
Approximate Spectral Clustering via Randomized Sketching

A. Gittens, A. Kambadur, C. Boutsidis.

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

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

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

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

Abstract

O. Bhardwaj, Y. Ineichen, C. Bekas, and A. Curioni

*SC 13*, 2013Abstract

Subspace Embeddings and $$\backslash$ ell\_p $-Regression Using Exponential Random Variables

David P Woodruff, Qin Zhang

David P Woodruff, Qin Zhang

*arXiv preprint arXiv:1305.5580*, 2013
Low rank approximation and regression in input sparsity time

Kenneth L Clarkson, David P Woodruff

http://arxiv.org/abs/1207.6365

Kenneth L Clarkson, David P Woodruff

*Proceedings of the 45th annual ACM symposium on theory of computing*,*pp. 81--90*, 2013http://arxiv.org/abs/1207.6365

Randomized Dimensionality Reduction for K-means Clustering

C. Boutsidis, A. Zouzias, M.W. Mahoney, and P. Drineas

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

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

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

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

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

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

Also available on arxiv: http://arxiv.org/abs/1201.0127

Haim Avron, Christos Boutsidis

*SIAM Journal on Matrix Analysis and Applications**34*(*4*), 2013Also available on arxiv: http://arxiv.org/abs/1201.0127

Efficient Dimensionality Reduction for Canonical Correlation Analysis

H. Avron, C. Boutsidis, S. Toledo, A. Zouzias

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

H. Avron, A. Druinsky, S. Toledo

*CoRR**abs/1301.1107*, 2013
Sketching Structured Matrices for Faster Nonlinear Regression

Haim Avron, Vikas Sindhwani, David Woodruff

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

Extended version appeared as an IBM Research Report (http://domino.research.ibm.com/library/cyberdig.nsf/papers/B6A6347CBFD55F4285257A1300500242)

Haim Avron, Satyen Kale, Shiva Kasiviswanathan, Vikas Sindhwani

*Proceedings of the 29th International Conference on Machine Learning (ICML)*, 2012Extended 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

Kenneth L Clarkson, Petros Drineas, Malik Magdon-Ismail, Michael W Mahoney, Xiangrui Meng, David P Woodruff

*arXiv preprint arXiv:1207.4684*, 2012**2011**

Effective Stiffness: Generalizing Effective Resistance Sampling to Finite Element Matrices

Haim Avron, Sivan Toledo

Haim Avron, Sivan Toledo

*CoRR**abs/1110.4437*, 2011
Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix

Haim Avron, Sivan Toledo

Abstract

Haim Avron, Sivan Toledo

*J. ACM**58*(*8*), 1-34, ACM, 2011Abstract

Topics in Matrix Sampling Algorithms

C. Boutsidis

C. Boutsidis

*Ph.D Dissertation, Rensselaer Polytechnic Institute*, 2011
Sparse Features for PCA-like Linear Regression

C. Boutsidis, P. Drineas, and M. Magdon-Ismail

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

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

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

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

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

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

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

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

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

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

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

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

Yi Li, Huy L Nguy\^en, David P Woodruff

researcher.ibm.com, 0