Low rank modeling is arguably the most ubiquitous paradigm of data analysis and related fields. Despite the many existing standard techniques and their useful applications, there has been an overflow of recent developments with fundamentally novel viewpoints and new kinds of applications. These include the completion of missing values of low-rank matrices, robust low-rank models with sparse corruptions, mixtures of low-rank models, structured dictionary learning and selective sampling of hierarchically-structured high-rank matrices. The goal of this workshop is to present some of the recent theoretical progress of low rank modeling and its important applications to imaging and computer vision.
Gilad Lerman, University of Minnesota, Twin Cities
The official program for the minisymposium is online: MS30 (session I) and MS52 (session II)
Abstract: In the standard form, PCA involves organizing data into a matrix where columns represent the points, and rows the features. We consider PCA in a challenging setting where there are outliers (i.e. some columns are completely arbitrary), and most data is missing (i.e. most elements of the matrix are not observed). We propose a recovery method based on convex optimization, and provide analytical guarantees on when it is able to both (a) recover the low-rank matrix, and (b) identify the outliers. These tasks are challenging for other methods, because they are coupled and have to be performed jointly.
Slides of Talk
10:00-10:25 A Novel M-Estimator for Robust PCA
Teng Zhang, University of Minnesota, USA; Gilad Lerman, University of Minnesota, USA
Abstract: We formulate a convex minimization to robustly recover a subspace from a contaminated data set, partially sampled around it, and propose a fast iterative algorithm to achieve the corresponding minimum. We establish exact recovery by this minimizer, quantify the effect of noise and regularization, explain how to take advantage of a known intrinsic dimension and establish linear convergence of the iterative algorithm. Our minimizer is an M-estimator. We demonstrate its significance by adapting it to formulate a convex minimization equivalent to the non-convex total least squares (which is solved by PCA). We compare our method with many other algorithms for Robust PCA on synthetic and real data sets and demonstrate state-of-the-art speed and accuracy.
Slides of Talk
10:30-10:55 Online Subspace Estimation and Tracking from Incomplete and Corrupted Data
Laura Balzano, University of Wisconsin, USA; Jun He, Nanjing University of Science & Technology, China; Arthur Szlam, New York University, USA; Brian Eriksson, Boston University, USA; Benjamin Recht and Robert Nowak, University of Wisconsin, USA
Abstract: Low-dimensional linear subspace approximations to high-dimensional data are useful for handling problems of estimation, detection and prediction, with applications such as network monitoring, collaborative filtering, object tracking in computer vision, and environmental sensing. Corrupted and missing data are the norm in many high-dimensional situations, not only because of errors and failures, but because it may be impossible to collect all the interesting measurements or impractical to compute in real-time using all the data available. Recently developed algorithms for "Matrix Completion" and "Robust PCA" have offered tools to find low-dimensional approximations to data even when data are missing and corrupted. However, these algorithms operate on all the available data at once and assume that the underlying low-dimensional subspace remains constant. In this talk I will describe two alternatives, a subspace tracking algorithm called GROUSE (Grassmannian Rank-one Update Subspace Estimation) and its robust counterpart GRASTA (Grassmannian Robust Adaptive Subspace Tracking Algorithm). Both are incremental algorithms that process one incomplete and/or corrupted measurement vector at a time. Thus GROUSE and GRASTA operate with considerably less computation than the other algorithms, while at the same time allowing flexibility for real-time applications such as tracking and anomaly detection. I will present these algorithms, discuss their relationship to LMS subspace tracking algorithms familiar to those in signal processing, and show their application to matrix completion, robust PCA, and background and foreground separation in video surveillance.
4:30-4:55 Dictionary Learning by L1 Minimization
John Wright, Columbia University, USA
Abstract: The idea that many important classes of signals can be well-represented by linear combinations of a small set of atoms selected from a given dictionary has had dramatic impact on the theory and practice of signal processing. For practical problems in which an appropriate sparsifying dictionary is not known ahead of time, a very popular and successful heuristic is to search for a dictionary that minimizes an appropriate sparsity surrogate over a given set of sample data. While this idea is appealing, the behavior of these algorithms is largely a mystery; although there is a body of empirical evidence suggesting they do learn very effective representations, there is little theory to guarantee when they will behave correctly, or when the learned dictionary can be expected to generalize. In this talk, we describe several steps toward such a theory. We show that under mild hypotheses, the dictionary learning problem is locally well-posed: the desired solution is indeed a local minimum of the L1 norm. Namely, if A is an incoherent (and possibly overcomplete) dictionary, and the coefficients X follow a random sparse model, then with high probability (A;X) is a local minimum of the L1 norm over the manifold of factorizations (A,X) satisfying AX = Y , provided the number of samples is sufficiently large. For overcomplete A, this is the first result showing that the dictionary learning problem is locally solvable. Our analysis draws on tools developed for the problem of completing a low-rank matrix from a small subset of its entries. We also discuss several restricted situations in which the problem can be solved globally by efficient algorithms. We motivate these problems with applications examples from image processing and computer vision, such as image super-resolution and hyperspectral image acquisition. We also draw connections to related problems in sparse vector and low-rank matrix recovery.
Slides of Talk
5:00-5:25 Robust Locally Linear Analysis with Applications to Image Denoising and Blind Inpainting
Yi Wang, University of Minnesota, USA; Arthur Szlam, New York University, USA; Gilad Lerman, University of Minnesota, USA
Abstract: I will talk about the problems of denoising images corrupted by impulsive noise and blind inpainting (i.e., inpainting when the deteriorated region is unknown). Our basic approach is to model the set of patches of pixels in an image as a union of low-dimensional subspaces, corrupted by sparse but perhaps large magnitude noise. For this purpose, we develop a robust and iterative method for single subspace modeling and extend it to an iterative algorithm for modeling multiple subspaces. I will also cover the convergence for the algorithm and demonstrate state of the art performance of our method for both imaging problems.
Slides of Talk
5:30-5:55 A Wide-Angle View of Image Filtering
Peyman Milanfar, University of California, Santa Cruz, USA
Abstract: Filtering 2- and 3-D data (i.e. images and video) is fundamental and common to many fields. From graphics, machine vision and imaging, to applied mathematics and statistics, important innovations have been introduced in the past decade which have advanced the state of the art in applications such as denoising and deblurring. While the impact of these contributions has been significant, little has been said to illuminate the relationship between the theoretical foundations, and the practical implementations. Furthermore, new algorithms and results continue to be produced, but generally without reference to fundamental statistical performance bounds. In this talk, I will present a wide-angle view of filtering, from the practical to the theoretical, and discuss performance analysis and bounds, indicating perhaps where the biggest (if any) improvements can be expected. Furthermore, I will describe various broadly applicable techniques for improving the performance of \textbf{any} given denoising algorithm in the mean-squared error sense, without assuming prior information, and based on the given noisy data alone.
Slides of Talk
6:00-6:25 Fast approximations to nearest subspace search and structured sparse coding, and applications to object classification
Arthur Szlam,City University of New York, USA; Karol Gregor, Janelia Farm, HHMI, USA; Yann LeCun, Courant Institute, USA
Abstract: We describe a method for fast approximation of sparse coding and nearest subspace search. The input space is subdivided by a binary decision tree, and we store a lookup table with the active set assignments and pseudoinverses for each leaf in the tree. We use the fast coding to get a real time version of the sparse coding sift pyramid object recognition system.
For further information on this event, please email Gilad Lerman at lerman(at)umn.edu.