20160921-32李兴国:Locating Outliers in Large Matrices with...

报告嘉宾2：李兴国（明尼苏达大学）

报告时间：2016年9月21日（星期三）晚21:00（北京时间）

报告题目：Locating Outliers in Large Matrices with Adaptive Compressive Sampling

主持人：赵拓（约翰霍普金斯大学/佐治亚理工大学）

报告摘要:

This paper examines the problem of locating outlier columns in a large, otherwise low-rank, matrix.  We propose a simple two-step adaptive sensing and inference approach and establish theoretical guarantees for its performance; our results show that accurate outlier identification is achievable using very few linear summaries of the original data matrix -- as few as the squared rank of the low-rank component plus the number of outliers, times constant and logarithmic factors.  We demonstrate the performance of our approach experimentally in two stylized applications, one motivated by robust collaborative filtering tasks, and the other by saliency map estimation tasks arising in computer vision and automated surveillance, and also investigate extensions to settings where the data are noisy, possibly incomplete, or has a known dictionary for the outliers.

参考文献:

 [1] X. Li and J. Haupt, “Identifying outliers in large matrices via randomized adaptive compressive sampling,” Trans. Signal Processing, vol. 63, no. 7, pp. 1792–1807, 2015.

[2] H. Xu, C. Caramanis, and S. Sanghavi, “Robust PCA via outlier pursuit,” IEEE Trans. Inform. Theory, vol. 58, no. 5, pp. 3047–3064, 2012.

[3] Y. Chen, H. Xu, C. Caramanis, and S. Sanghavi, “Matrix completion with column manipulation: Near-optimal sample-robustness-rank tradeoffs,” IEEE Trans. Inform. Theory, vol. 62, no. 1, pp. 503–526, 2016.

[4] David P. Woodruff, “Sketching as a tool for numerical linear algebra,” Found. Trends Theor. Comput. Sci., vol. 10, no. 1–2, pp. 1–157, Oct. 2014.Biography:

报告人简介: 

Xingguo Li is a PhD student in Department of Electrical and Computer Engineering at University of Minnesota (UMN). His research focuses on statistical signal processing, high-dimensional statistical optimization with applications to image processing and computer vision. Prior to joining UMN, he received the B.E. in Communications Engineering from Beijing University of Posts and Telecommunications, and M.S. with honor in Applied Mathematics from University of Minnesota Duluth. He was a visiting researcher in school of computer science, Carnegie Mellon University.