LNLA 2009

Abstract: Principal component analysis is a fundamental operation in computational data analysis, with myriad applications ranging from web search, to bioinformatics, to dynamical system identification, to computer vision and image analysis. However, its performance and applicability in real scenarios are limited by a lack of robustness to outlying or corrupted observations. In this work, we consider the idealized "robust principal component analysis" problem of recovering a low-rank matrix A from corrupted observations D = A + E. Here, the error entries E can be arbitrarily large (modeling grossly corrupted observations common in visual and bioinformatic data), but are assumed to be sparse. We prove that most matrices A can be efficiently and exactly recovered from most error sign-and-support patterns, by solving a simple convex program. Our result holds even when the rank of A grows nearly proportionally (up to a logarithmic factor) to the dimensionality of the observation space and the number of errors E grows in proportion to the total number of entries in the matrix. A by-product of our analysis is the first proportional growth results for the related but somewhat easier problem of completing a low-rank matrix from a small fraction of its entries. We propose a provably convergent algorithm based on proximal gradient and iterative thresholding that, for large matrices, is significantly faster and more scalable than general-purpose solvers. We provide simulations and real-data examples corroborating the theoretical results. The simulation results actually have revealed even more striking phenomena and remarkable pictures that merit future investigation.

This is joint work with my students John Wright, Arvind Ganesh, and Shankar Rao.

Abstract: In Signal and Image Processing, similarly to many other fields of human endeavor, people are seeking the best solutions to the various problems that arise. The noble search for optimality, and the beautiful solutions that are sometimes found, are overshadowed by the relativity of the achievement: the optimal solutions are best only with respect to cost functions or functionals for which there are no objective means of evaluation. This issue will be the topic of discussion, with examples provided from the field of variational denoising, several fundamental inverse problems in image analysis and sparse signal representations.

Abstract: A generic principle is presented for forming multiplicative update rules, which integrate orthonormality into nonnegative learning. The principle, called Orthogonal Nonnegative Learning (ONL), is rigorously derived from the Lagrangian technique. As an example, the proposed method is applied for transforming Nonnegative Matrix Factorization and its variants into their orthogonal versions. Also, an on-line positive PCA rule is derived.

In general, such orthogonal nonnegative learning can give very useful approximative solutions for problems involving non-vectorial data, for example, binary solutions. Combinatorial optimization is replaced by continuous-space gradient optimization which is often computationally lighter. Another application is sparse compression because orthogonal non-negative vectors are sparse.

It is shown how the multiplicative update rules obtained by using the proposed ONL principle can find a nonnegative and highly orthogonal matrix for an approximated graph partitioning problem. The empirical results on various graphs indicate that our nonnegative learning algorithms not only outperform those without the orthogonality condition, but also surpass some other existing partitioning approaches. Also results on image compression are shown.

Abstract: Communication and computing applications are more and more visually oriented containing images, videos and graphics. A good example of the speed of development are the smart phones where camera resolutions start to be in the five megapixel range, a number that was considered too high for any relevant application some years ago. Development of high performance low power computing environments and move to 3G wireless networks and mobile internet have been instrumental for this development. On the other hand, rich multimedia already today tends to take a lion's share of the computing and communication capabilities of a system. This presentation will look at the opportunities, challenges and constraints which the more and more visually oriented applications are likely to meet in the coming years. I will also discuss the importance of international cooperation and funding as essential elements in this kind of forward looking research.