The ubiquitous availability of high-dimensional data such as images and videos has generated a lot of interest in data analysis. The key motivation to develop new tools for analysis is the fact that most real world data has some underlying degenerate low-dimensional structure. However, in practice, we never observe this degenerate structure because real data is often corrupted with irrelevant measurements. For image data, there is also the problem of deformations or domain transformations that can cause images of the same object or scene to have very different appearances when viewed from different positions.

Low-rank matrix approximation methods, such as the Principal Component Analysis (PCA), are very popular in practical applications. Recently, it was shown that low-rank matrices can be recovered exactly from grossly corrupted measurements via convex optimization. This framework, called Principal Component Pursuit (PCP), constitutes a powerful tool that allows us to handle corrupted measurements and even missing entries in a principled way. We present here two applications in computer vision where PCP and its variants can be used to exploit the low-rank structure inherent in image data. In particular, we apply these techniques to align multiple images of a scene simultaneously as well as to exploit the internal symmetries in an image to study its 3-D structure or to find novel transformation invariant representations of it.