{"205791":{"#nid":"205791","#data":{"type":"event","title":"ARC Colloquium: David Woodruff, IBM Almaden Research Center, San Jose, CA.","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E Low Rank Approximation and Regression in Input Sparsity Time \u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EWe improve the running times of algorithms for least squares regression and low-rank approximation to account for the sparsity of the input matrix. \u0026nbsp;Namely, if nnz (A) denotes the number of non-zero entries of an input matrix A: \u003C\/p\u003E\u003Cul\u003E\u003Cli\u003Ewe show how to solve approximate least squares regression given an n x d matrix A in nnz(A) + poly(d log n) time \u003C\/li\u003E\u003Cli\u003Ewe 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 \u003C\/li\u003E\u003C\/ul\u003E\u003Cp\u003EAll 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. \u003C\/p\u003E\u003Cp\u003EJoint work with Ken Clarkson.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":"","uid":"27263","created_gmt":"2013-04-11 10:39:17","changed_gmt":"2016-10-08 02:03:16","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2013-04-26T11:00:00-04:00","event_time_end":"2013-04-26T11:00:00-04:00","event_time_end_last":"2013-04-26T11:00:00-04:00","gmt_time_start":"2013-04-26 15:00:00","gmt_time_end":"2013-04-26 15:00:00","gmt_time_end_last":"2013-04-26 15:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"47223","name":"College of Computing"},{"id":"50875","name":"School of Computer Science"},{"id":"50877","name":"School of Computational Science and Engineering"},{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003E\u003Ca href=\u0022mailto:ndongi@cc.gatech.edu\u0022\u003Endongi@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}