from    
to    
search  

 


Symmetry restoration and quantum Mpemba effects in chaotic andlocalization sy...
Quantum Gases 2024
Stories of Fermions in an Optical Box
Contractive Unitary and Classical Shadow Tomography
报告题目:
Low Rank Approximation and Regression in Input Sparsity Time
 报告人:
Dr. David P Woodruff
IBM Almaden
报告时间:
2012-09-10 16:00
报告地点:
FIT 1-222
主办单位:
交叉信息研究院
  简介:

Abstract

We improve the running times of algorithms for least squares regression and low-rank approximation to account for the sparsity of the input matrix. Namely, if nnz(A) denotes the number of non-zero entries of an input matrix A:- we show how to solve approximate least squares regression given an n x d matrix A in nnz(A) + poly(d log n) time- we show how to find an approximate best rank-k approximation of an n x n matrix in nnz(A) + n*poly(k log n) time. All approximations are relative error. Previous algorithms based on fast Johnson-Lindenstrauss transforms took at least ndlog d or nnz(A)*k time. We have implemented our algorithms, and preliminary results suggest the algorithms are competitive in practice.

Joint work with Ken Clarkson.

今日相关信息
周光召基金会获奖者清华论坛
 
同类别相关信息
活动因故取消,请大家相互转告!MSTA ...
清华大学电机系“景德讲坛”首讲:抢抓电...
清华中医药交叉学术沙龙:中医瑰宝 黄帝...
信息大讲堂第183讲:Future Wireless I...
Hybrid Transaction and Analytics Pr...
学术活动