Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, May 02, 2017, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Kenneth Clarkson (IBM Research Almaden)
A number of matrices that arise in machine learning and data analysis are symmetric positive semidefinite (PSD), including covariance matrices, kernel matrices, Laplacian matrices, random dot product graph models, and others. A common task related to such matrices is to approximate them with a low-rank matrix, for efficiency or statistical inference; spectral clustering, kernel PCA, manifold learning, and Gaussian process regression can all involve this task. Given a square n by n matrix A, target rank k, and error parameter epsilon, we show how to find a PSD matrix B of rank k, such that the Frobenius norm of A-B is within (1+epsilon) of best possible; our algorithm needs O(nnz(A) + n*poly(k/epsilon)) time to do this, where nnz(A) is the number of nonzero entries of A. We also show how to find such a rank-k matrix PSD B of the form CUC^T, where the O(k/eps) columns of C are a subset of those of A, with a similar runtime. Joint work with David Woodruff.
Automatic MiSe System Software Version 1.4803M | admin login