Timezone: »

 
Poster
Global Solver and Its Efficient Approximation for Variational Bayesian Low-rank Subspace Clustering
Shinichi Nakajima · Akiko Takeda · S. Derin Babacan · Masashi Sugiyama · Ichiro Takeuchi

Fri Dec 06 07:00 PM -- 11:59 PM (PST) @ Harrah's Special Events Center, 2nd Floor
in Poster Session »

When a probabilistic model and its prior are given, Bayesian learning offers inference with automatic parameter tuning. However, Bayesian learning is often obstructed by computational difficulty: the rigorous Bayesian learning is intractable in many models, and its variational Bayesian (VB) approximation is prone to suffer from local minima. In this paper, we overcome this difficulty for low-rank subspace clustering (LRSC) by providing an exact global solver and its efficient approximation. LRSC extracts a low-dimensional structure of data by embedding samples into the union of low-dimensional subspaces, and its variational Bayesian variant has shown good performance. We first prove a key property that the VB-LRSC model is highly redundant. Thanks to this property, the optimization problem of VB-LRSC can be separated into small subproblems, each of which has only a small number of unknown variables. Our exact global solver relies on another key property that the stationary condition of each subproblem is written as a set of polynomial equations, which is solvable with the homotopy method. For further computational efficiency, we also propose an efficient approximate variant, of which the stationary condition can be written as a polynomial equation with a single variable. Experimental results show the usefulness of our approach.

[ PDF] 

Author Information

Shinichi Nakajima (TU Berlin)
Akiko Takeda (The University of Tokyo / RIKEN)
S. Derin Babacan (Google Research)
Masashi Sugiyama (RIKEN / University of Tokyo)
Ichiro Takeuchi (Nagoya Institute of Technology)

More from the Same Authors