Global Solver and Its Efficient Approximation for Variational Bayesian Low-rank Subspace Clustering
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 consists of 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.
The problem of low rank subspace clustering can be 
      addressed by variational Bayes, with the advantage over MAP methods that 
      the rank is adjusted automatically, and virtually no free parameters have 
      to be tuned. The posterior variances also possibly give more information. 
      As reviewed by the authors (I am not familiar with this 
      literature), subspace clustering seems to optimize for an affinity matrix 
      to be put into spectral clustering, by essentially regressing datapoints 
      onto themselves with low rank constraint. The method here tackles the 
      first step, how to obtain the affinity matrix. This can be done by 
      variational Bayes. Given that the error is measured by Frobenius norm and 
      that all observations are complete (I wonder how realistic that is), 
      recent results [18] can be adapted to solve this VB problem by a singular 
      value decomp. of the data matrix plus mapping the SVs one by one, using 
      some complicated polynomial equations, which however can be solved 
      analytically. In particular after a 2nd constraint, the latter is just 
      O(L), no iterations are needed. The global optimum is found, even 
      including hyperparameters (prior variances). Given that (a) 
      subspace clustering is a useful problem, and (b) VB is a good method for 
      doing it, the results here are very good and very useful. I cannot 
      comment on (a), (b), they cite some papers in computer vision. I am a 
      big fan of [18]. What is done here is closely related, but some additional 
      new ideas (homotopy method) are needed. Just as with [18], it is easy to 
      understand the basic idea just by looking at the Frobenius error, but very 
      hard to check the details: I assume they are correct. The 
      experimental evaluation is convincing, but they could make a larger effort 
      describing the context. What is clustered here? What is the clustering 
      error? In order to save space, throw out the equations on iterative VB: 
      nobody needs them anymore after this paper! Also, please give proof 
      sketches. Here, you do not even state clearly why X diagonalizes in the 
      right SV basis -- this is easy to argue for. Also, why did you not 
      compare against the simpler MAP solution of (2)? Previous work did not 
      seem to employ VB at all, except for [2] (non-empty overlap with the 
      authors here?), so I find it odd to only compare against a rather esoteric 
      variant -- if another globally solvable method is available. 
      Finally, the main limitation of all this work is that I cannot 
      have a weighted error, in particular the data matrix Y has to be 
      completely observed. It may be good to comment on whether this is an issue 
      in the application here.