{"448851":{"#nid":"448851","#data":{"type":"event","title":"ARC Colloquium: David P. Woodruff - IBM","body":[{"value":"\u003Ch2 align=\u0022center\u0022\u003EDavid P. Woodruff - IBM\u003C\/h2\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, November 9, 2015\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 West \u2013 1:00 pm\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003E(Refreshments will be served in Klaus 2222 at 2 pm)\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003Cstrong\u003ETitle: \u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EInput Sparsity Time Algorithms for Robust Regression and Robust Low Rank Approximation\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EWe give near optimal algorithms for regression and low rank approximation in the robust case. For regression, we give algorithms generalizing l_p regression to M-Estimator loss functions, such as the Huber measure, which enjoys the robustness properties of l_1 as well as the smoothness properties of l_2. For low rank approximation, we give new algorithms generalizing the singular value decomposition to sum of p-th powers of distances, and M-estimator loss functions applied to the distances. Some problems here are arguably even more fundamental than the SVD itself, such as given a set of points, find a line which minimizes the sum of distances of the points to the line, rather than the sum of squared distances. These measures are less sensitive to outliers and we show they can be computed approximately in time proportional to the number of non-zeros of the input matrix. We also discuss hardness results in the low rank approximation setting.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Klaus 1116 West at 1 pm"}],"uid":"27466","created_gmt":"2015-09-16 14:39:24","changed_gmt":"2017-04-13 21:18:16","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2015-11-09T12:00:00-05:00","event_time_end":"2015-11-09T13:00:00-05:00","event_time_end_last":"2015-11-09T13:00:00-05:00","gmt_time_start":"2015-11-09 17:00:00","gmt_time_end":"2015-11-09 18:00:00","gmt_time_end_last":"2015-11-09 18:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[{"id":"111051","name":"Algorithm and Randomness Center"},{"id":"4265","name":"ARC"},{"id":"115001","name":"Computational Complexity"},{"id":"114991","name":"Computational Learning Theory"},{"id":"109","name":"Georgia Tech"},{"id":"1126","name":"ibm"},{"id":"9167","name":"machine learning"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78751","name":"Undergraduate students"},{"id":"78761","name":"Faculty\/Staff"},{"id":"78771","name":"Public"},{"id":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EDani Denton\u003Cbr \/\u003Edenton at cc dot gatech dot edu\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}