Matrix Factorization This Week.

Today we have five papers, a poster and one code in the advanced matrix factorization world:

First we start with a team that took up data from the Kinect to show how good their tracker system was. The issue at hand in motion registration is trying to identify the features from one frame to the other that provide real information about the motion of objects. One always face issues with outliers and this paper show how they use the robust PCA (PCP) with some additional constraint to make that motion estimation a robust process.

Sparse Online Low-Rank Projection and Outlier Rejection (SOLO) for 3-D Rigid-Body Motion Registration by Chris Slaughter, Allen Y. Yang, Justin Bagwell, Costa Checkles, Luis Sentis, Sriram Vishwanath. The abstract reads:

Motivated by an emerging theory of robust low-rank matrix representation, in this paper, we introduce a novel solution for online rigid-body motion registration. The goal is to develop algorithmic techniques that enable a robust, real-time motion registration solution suitable for low-cost, portable 3-D camera devices. Assuming 3-D image features are tracked via a standard tracker, the algorithm first utilizes Robust PCA to initialize a low-rank shape representation of the rigid body. Robust PCA finds the global optimal solution of the initialization, while its complexity is comparable to singular value decomposition. In the online update stage, we propose a more efficient algorithm for sparse subspace projection to sequentially project new feature observations onto the shape subspace. The lightweight update stage guarantees the real-time performance of the solution while maintaining good registration even when the image sequence is contaminated by noise, gross data corruption, outlying features, and missing data. The state-of-the-art accuracy of the solution is validated through extensive simulation and a real-world experiment, while the system enjoys one to two orders of magnitude speed-up compared to well-established RANSAC solutions. The new algorithm will be released online to aid peer evaluation.

I still note that "It shows the accuracy of RPCA is still sensitive to high variance dense Gaussian noise." The code that perform this SOLO refinement over a plain vanilla RPCA solver will be available on the author's website at some point in time according to the paper.

Next, we have Online Robust Subspace Tracking from Partial Information by Jun He, Laura Balzano, John C.S. Lui. The abstract reads:

This paper presents GRASTA (Grassmannian Robust Adaptive Subspace Tracking Algorithm), an efficient and robust online algorithm for tracking subspaces from highly incomplete information. The algorithm uses a robust $l^1$-norm cost function in order to estimate and track non-stationary subspaces when the streaming data vectors are corrupted with outliers. We apply GRASTA to the problems of robust matrix completion and real-time separation of background from foreground in video. In this second application, we show that GRASTA performs high-quality separation of moving objects from background at exceptional speeds: In one popular benchmark video example, GRASTA achieves a rate of 57 frames per second, even when run in MATLAB on a personal laptop.

No implementation is available for the moment.

Finally, we have: Sparse PCA via Augmented Lagrangian Methods and Application to Informaitve Feature Selection by Nikhil Naikal, Allen Y. Yang, S. Shankar Sastry. The abstract reads:

Bag-of-words (BoW) methods are a popular class of object recognition methods that use image features (e.g., SIFT) to form visual dictionaries and subsequent histogram vectors to represent object images in the recognition process. The accuracy of the BoW classifiers, however, is often limited by the presence of uninformative features extracted from the background or irrelevant image segments. Most existing solutions to prune out uninformative features rely on enforcing pairwise epipolar geometry via an expensive structure-from-motion (SfM) procedure. Such solutions are known to break down easily when the camera transformation is large or when the features are extracted from lowresolution, low-quality images. In this paper, we propose a novel method to select informative object features using a more efficient algorithm called Sparse PCA. First, we show that using a large-scale multiple-view object database, informative features can be reliably identified from a highdimensional visual dictionary by applying Sparse PCA on the histograms of each object category. Our experiment shows that the new algorithm improves recognition accuracy compared to the traditional BoW methods and SfM methods. Second, we present a new solution to Sparse PCA as a semidefinite programming problem using the Augmented Lagrangian Method. The new solver outperforms the state of the art for estimating sparse principal vectors as a basis for a low-dimensional subspace model

The source code for this instance of Sparse PCA using ALM method can be found here and is listed on the Matrix Factorization Jungle page.

Fast and Robust Appearance-based Tracking by Stephan Liwicki, Stefanos Zafeiriou, Georgios Tzimiropoulos and Maja Pantic. The abstract reads:

 We introduce a fast and robust subspace-based approach to appearance-based object tracking. The core of our approach is based on Fast Robust Correlation (FRC), a recently proposed technique for the robust estimation of large translational displacements. We show how the basic principles of FRC can be naturally extended to formulate a robust version of Principal Component Analysis (PCA) which can be efficiently implemented incrementally and therefore is particularly suitable for robust real-time appearance-based object tracking. Our experimental results demonstrate that the proposed approach outperforms other state-of-the-art holistic appearance-based trackers on several popular video sequences.

The attendant poster is Fast and robust appearance-based tracking .

And finally, we have:

The inclusion of dictionary learning capabilty within scikit.learn a python package in version 0.9

and

Low-rank Matrix Recovery from Errors and Erasures by Yudong Chen, Ali Jalali, Sujay Sanghavi, Constantine Caramanis. The abstract reads:

This paper considers the recovery of a low-rank matrix from an observed version that simultaneously contains both (a) erasures: most entries are not observed, and (b) errors: values at a constant fraction of (unknown) locations are arbitrarily corrupted. We provide a new unified performance guarantee on when the natural convex relaxation of minimizing rank plus support succeeds in exact recovery. Our result allows for the simultaneous presence of random and deterministic components in both the error and erasure patterns. On the one hand, corollaries obtained by specializing this one single result in different ways recover (up to poly-log factors) all the existing works in matrix completion, and sparse and low-rank matrix recovery. On the other hand, our results also provide the first guarantees for (a) recovery when we observe a vanishing fraction of entries of a corrupted matrix, and (b) deterministic matrix completion.

There is currently no release of any implementation of this group, which really means that they are not featured on the Matrix Factorization Jungle page...as we say in Texas, it's a damn shame.



Liked this entry ? subscribe to the Nuit Blanche feed, there's more where that came from