Adaptive graph-regularized fixed rank representation for subspace segmentation

Abstract

Low-rank representation (LRR) has shown its great power in subspace segmentation tasks. However, by using matrix factorization skill, fixed-rank representation dominates LRR in many subspace segmentation applications. In this paper, based on the depth analyses on fixed-rank representation (FRR), we propose a new graph-regularized FRR method which is termed adaptive graph-regularized fixed-rank representation (AGFRR). Different from the existing methods which use the original data set to build the graph regularizer for a reconstruction coefficient matrix, AGFRR uses one of the matrix factor of a reconstruction matrix to construct the graph regularizer for the reconstruction matrix itself. We claim that the constructed graph regularizer can discover the manifold structure of a given data set more faithfully. Hence, AGFRR is more suitable for revealing the nonlinear subspace structures of data sets than FRR. Moreover, an optimization algorithm for solving AGFRR problem is also provided. Finally, the subspace segmentation experiments on both synthetic and real-world data sets show that AGFRR is superior to the existing LRR and FRR-related algorithms.

Appendix

By following the methodology of linear ADM [28], the augmented Lagrangian function of Eq. (4) can be presented as follows:

$$\begin{aligned} \mathbf {L}= & {} \Vert \mathbf {Z}-\mathbf {WV}\Vert _F^2+\beta \mathcal {R}(\mathbf {Z,V})\nonumber \\&+\lambda \Vert \mathbf {E}\Vert _{2,1} +<\mathbf {Y}_1,\mathbf {X-XZ-E}>\nonumber \\&+ <\mathbf {Y}_2,\mathbf {1}_n\mathbf {Z}-\mathbf {1}_n>+\mu /2\big (\Vert \mathbf {X-XZ-E}\Vert _F^2\nonumber \\&+\Vert \mathbf {1}_n\mathbf {Z}-\mathbf {1}_n\Vert _F^2\big ). \end{aligned}$$

(16)

Then the variables $\mathbf {V}$, $\mathbf {W}$, $\mathbf {Z}$ and $\mathbf {E}$ can be optimized by alternately minimizing $\mathbf {L}$. The methods for updating $\mathbf {V}$, $\mathbf {W}$ and $\mathbf {E}$ are similar to those in Algorithm 1. Hence, we focus on how to optimize $\mathbf {Z}$ (Fig. 5).

UpdateZwith fixed other variables We abandon the irrelevant terms w.r.t $\mathbf {Z}$ in Eq. (16), then we have

$$\begin{aligned}&\min \nolimits _{\mathbf {Z}} \Vert \mathbf {Z}-\mathbf {W}\mathbf {V}\Vert _F^2+\beta \mathcal {R}(\mathbf {Z,V})+\langle \mathbf {Y}_1,\mathbf {X-XZ}-\mathbf {E}\rangle \nonumber \\&\qquad +\langle \mathbf {Y}_2,\mathbf {1}_n\mathbf {Z}-\mathbf {1}_n\rangle \mu /2\big (\Vert \mathbf {X-XZ}-\mathbf {E}\Vert _F^2+\Vert \mathbf {1}_n\mathbf {Z}-\mathbf {1}_n\Vert _F^2\big ),\nonumber \\&\quad =\min \nolimits _{\mathbf {Z}} \Vert \mathbf {Z}-\mathbf {W}\mathbf {V}\Vert _F^2+\beta tr(\mathbf {Z}\mathbf {L_V}\mathbf {Z}^T)\nonumber \\&\qquad +\mu /2\big (\Vert \mathbf {X-XZ}-\mathbf {E}+\mathbf {Y}_1/\mu \Vert _F^2\nonumber \\&\qquad +\Vert \mathbf {1}_n\mathbf {Z}-\mathbf {1}_n+\mathbf {Y}_2/\mu \Vert _F^2\big ). \end{aligned}$$

(17)

By Taking the derivative of the above problem w.r.t $\mathbf {Z}$ and setting it to be zero, the following equation holds:

$$\begin{aligned}&\big [2\mathbf {I}_n+\mu (\mathbf {X}^T\mathbf {X}+\mathbf {1}_n^T\mathbf {1})\big ]\mathbf {Z}+2\beta \mathbf {Z}\mathbf {L_v}\nonumber \\&\quad -\mu \big [\mathbf {X}^T(\mathbf {X}-\mathbf {E}+\mathbf {Y}_1/\mu ) +\mathbf {1}_n^t(\mathbf {1}_n-\mathbf {Y}_2/\mu )\big ]=0. \end{aligned}$$

(18)

It can be seen that Eq. (18) is a Sylvester equation [32] w.r.t. $\mathbf {Z}$, which can be solved by using the MATLAB function lyap().

Then the entire algorithmic procedure for solving Problem (4) by using linear ADM could be summarized in Algorithm 2.