# LogDet Rank Minimization with Application to Subspace Clustering

Authors: Zhao Kang; Chong Peng; Jie Cheng; Qiang Cheng
Journal: Computational Intelligence and Neuroscience
 (2015)

---

## Abstract

Low-rank matrix is desired in many machine learning and computer vision problems. Most of the recent studies use the nuclear norm as a convex surrogate of the rank operator. However, all singular values are simply added together by the nuclear norm, and thus the rank may not be well approximated in practical problems. In this paper, we propose using a log-determinant (LogDet) function as a smooth and closer, though nonconvex, approximation to rank for obtaining a low-rank representation in subspace clustering. Augmented Lagrange multipliers strategy is applied to iteratively optimize the LogDet-based nonconvex objective function on potentially large-scale data. By making use of the angular information of principal directions of the resultant low-rank representation, an affinity graph matrix is constructed for spectral clustering. Experimental results on motion segmentation and face clustering data demonstrate that the proposed method often outperforms state-of-the-art subspace clustering algorithms.


---

## Body

## 1. Introduction

Matrix rank minimizing [1] is ubiquitous in machine learning, computer vision, control, signal processing, and system identification. For instance, low-rank representation based subspace clustering [2–4] and matrix completion [5, 6] methods have achieved great success recently. Subspace clustering [7] is one of the fundamental topics with numerous applications, for example, image representation [8, 9], face clustering [3, 10], and motion segmentation [11, 12]. It is assumed that high-dimensional data is more likely a union of low-dimensional subspaces rather than one individual subspace. For example, different subspaces are needed to describe trajectories of different moving objects in a video sequence. Subspace clustering is an intrinsically difficult problem, since we need to simultaneously cluster all data points into multiple groups and find a low-dimensional subspace fitting each group of points.Subspace clustering has been an active research topic over the past decades. Four main categories of methods are proposed [10]: iterative, algebraic, statistical, and spectral clustering-based methods. The first three kinds of approaches are sensitive to initialization, noise, and outliers; in addition, they are difficult to optimize [10]. Spectral clustering-based methods have achieved promising performance, where the key is to learn a good affinity matrix of data points. For instance, the algorithms of local subspace affinity (LSA) [13], locally linear manifold clustering (LLMC) [14], and spectral local best-fit flats (SLBF) [15] use local information around each point to construct the affinity matrix, while spectral curvature clustering (SCC) [16] method preserves the global structures of the whole dataset in deriving the affinity matrix. Subsequently, K-means [17] or Normalized Cuts (NCuts) [18, 19] are applied to the affinity matrix to obtain clustering results.Recently, some spectral clustering-based methods, such as sparse representation (SSC) [10] and low-rank representation (LRR) [3], have been proposed to obtain state-of-the-art results in subspace clustering. SSC represents each data point as a sparse linear combination of the other points and solves an l
1-norm regularized minimization problem for sparsity. SSC shows promising results if the subspaces are either independent or disjoint [20].The basic idea of LRR is to learn a low-rank representation of data by capturing the global Euclidean structure of the whole data. In this scheme, each data point is represented as a linear combination of the examples in the data matrix itself, and a convex nuclear norm minimization is used as a surrogate of the rank function to obtain the desired low-rank representation. Though its optimization is well studied and has a global optimum, its performance may be far from optimal in real applications because the nuclear norm might not be a good approximation to the rank function. Compared to the rank function to which all nonzero singular values have equal contributions, the nuclear norm treats those values differently by simply adding them together. As a result, the nuclear norm may be dominated by a few very large singular values and significantly deviated from the true value of the rank. Several papers have considered this problem of using the nuclear norm and designed methods to alleviate it by either thresholding or removing some of the singular values; for instance, singular value thresholding [21] and truncated nuclear norm [6] both considerably enhance the performance of matrix completion.In this paper, we propose using a log-determinant (LogDet) function for rank approximation and study its minimization in subspace clustering. Different from the nuclear norm-based approaches which minimize the summation of all singular values, our approach aims to minimize the rank by making the contribution to be much closer to one from a big singular value, while being zero from a small singular value. In this way, we can get closer and more robust approximation to the rank function than the nuclear norm. Since the LogDet function is nonconvex, we apply the method of augmented Lagrange multipliers (ALM) to solve the associated optimization for potentially large-scale applications, in which the subproblem for minimizing the LogDet function in each iteration has a closed-form solution. To demonstrate the effectiveness of our LogDet minimization method, we apply it to subspace clustering. By employing a rather simple formulation based on the LogDet function, we obtain a low-rank representation for subspace clustering. Subsequently, we exploit the angular information of principal directions of such a representation to further enhance the separation ability of the affinity matrix. In summary, our main contributions of this work include the following.(i)
More accurate and robust rank approximation is used to obtain the low-rank representation, which is able to capture the global structure of the dataset.
(ii)
An iterative optimization algorithm is designed for minimizing this rank approximation-based objective function. Theoretical analysis shows that our algorithm converges to a stationary point. Specifically, the proposed optimization method is applied to subspace clustering.
(iii)
Angular information of principal directions of the low-rank representation is employed to further exploit the intrinsic local geometrical structure relevant to the membership of data points.
(iv)
Extensive experiments demonstrate the effectiveness of the proposed LogDet minimization method for rank approximation. Particularly, when used for subspace clustering, our simple formulation shows favorable performance compared to other state-of-the-art methods, although we do not explicitly account for outliers in our model. This demonstrates the robustness of our approach.The remainder of the paper is organized as follows: Section 2 provides a brief review of LRR and SSC. In Section 3, we present the proposed approximation and design an efficient optimization scheme. We give convergence analysis in Section 4. Experimental results are shown in Section 5. Finally, conclusions are drawn in Section 6.


## 2. Review of LRR and SCC

In this section, we give a brief review of SSC and LRR.LetX
=
[
x
1
,
x
2
,
…
,
x
n
]
∈
R
d
×
n be a set of d-dimensional data points drawn from an unknown union of k linear subspaces S
1
,
S
2
,
…
,
S
k. The task of subspace clustering is to segment data points into k subspaces.LRR tries to seek the lowest rank representation among many possible linear combinations of the bases in a given dictionary, which typically is the data matrix itself. The problem can be formulated as(1)
min
⁡
Z
rank
⁡
Z
s.t.
X
=
X
Z
,where Z
=
[
z
1
,
z
2
,
…
,
z
n
] is the coefficient matrix with each z
i being the representation of x
i. The above problem is NP-hard due to the combinatorial nature of the rank function.The tightest convex relaxation of the rank function [22] is the nuclear norm. For a matrix D
∈
R
m
×
n, its nuclear norm is defined as D
∗
=
∑
i
=
1
m
i
n
(
m
,
n
)
‍
σ
i
(
D
), where σ
i
(
D
) means the ith singular value of D. Using this relaxation, LRR solves the following problem:(2)
m
i
n
Z
Z
∗
s.t.
X
=
X
Z
.After obtaining Z, the affinity matrix W is defined as(3)
W
=
Z
+
Z
T
.Then the spectral clustering algorithm, Normalized Cuts [18], is used to produce the final segmentation.SSC aims to find a sparse representation ofX by solving the following convex optimization problem:(4)
min
⁡
Z
,
E
,
S
Z
1
+
α
2
E
F
2
+
γ
S
1
,
s.t.
X
=
X
Z
+
E
+
S
,
diag
⁡
Z
=
0
,where S
1
=
∑
i
j
‍
S
i
j, S is a sparse matrix containing the gross error, E
F
2
=
∑
i
‍
∑
j
‍
E
i
j
2, and E is a matrix of fitting residuals. After obtaining Z, subsequent procedures are similar to LRR.


## 3. LogDet Rank Approximation and Its Minimization Algorithm

A functionf
:
R
n
→
[
-
∞
,
∞
] is absolutely symmetric if f
(
x
) is invariant under arbitrary permutations and sign changes of the elements of x. Based on this function f
(
x
), we have the following theorem [23].Theorem 1.
FunctionF
:
R
n
1
×
n
2
→
R is unitarily invariant if F
(
X
)
=
f
(
σ
(
X
)
)
=
f
∘
σ
(
X
), where X
∈
R
n
1
×
n
2, whose singular value decomposition is X
=
U
diag
⁡
(
{
σ
i
}
1
≤
i
≤
n
)
V
T, σ
(
X
)
:
R
n
1
×
n
2
→
R
n are singular values of X, and n
=
min
⁡
(
n
1
,
n
2
). And the gradient of F
(
X
) at X is(5)
∂
F
X
∂
X
=
U
diag
⁡
θ
V
T
,where θ
=
∂
f
(
y
)
/
∂
y
y
=
σ
(
X
).Equation (5) can be obtained directly from Theorem 3.1 of [23].In this work, we utilize unitarily invariant function LogDet to achieve a closer, though not convex, rank relaxation than the nuclear norm. We apply the method of ALM for LogDet rank approximation associated minimization. To explain our method, we specifically consider using LogDet as a rank surrogate in subspace clustering. We first obtain a low-rank representation of high-dimensional data based on the LogDet optimization. Then we construct an affinity graph matrix for spectral clustering by using the angular information of principal directions of the low-rank representation.


### 3.1. LogDet Rank Minimization

We useLogDet
⁡
(
I
+
Z
T
Z
) as a surrogate of the rank function of Z. It is obvious that LogDet
⁡
(
I
+
Z
T
Z
)
=
∑
i
=
1
n
‍
log
⁡
(
1
+
σ
i
2
(
Z
)
). Because it can be easily verified that l
o
g
(
1
+
σ
i
2
(
Z
)
)
≤
σ
i
(
Z
) for any σ
i
(
Z
)
≥
0, we always have LogDet
⁡
(
I
+
Z
T
Z
)
≤
Z
∗; particularly, if there are large nonzero singular values, the LogDet function will be much smaller than the nuclear norm since l
o
g
(
1
+
σ
i
2
(
Z
)
)
≪
σ
i
(
Z
) for a large σ
i
(
Z
)
>
1. It is noted that, for small nonzero singular values, their contribution to the LogDet function will be significantly reduced compared to the nuclear norm. Because small nonzero singular values are often regarded as being from noise in the data, the LogDet function reduces noise effect more compared to the nuclear norm.It is worthwhile to note that a similar functionLogDet
⁡
(
X
+
δ
I
) was proposed in [24] to approximate rank and iterative linearization was used to find a local minimum. However, δ is a very small constant (e.g., 1
0
-
6), which leads to biased approximation for small singular values.This LogDet function is differentiable with respect to the singular values by Theorem1, and even though it is nonconvex, its minimization is rather simple by using our optimization method. To explain its minimization, we consider its specific application to subspace clustering. By employing the above LogDet function, we simply formulate the subspace clustering into the following unconstrained nonconvex minimization problem:(6)
min
Z
⁡
LogDet
⁡
I
+
Z
T
Z
+
ρ
X
-
X
Z
F
2
,where I
∈
R
n
×
n is the identity matrix. The first term of (6) is to minimize the rank of Z, while the second is a relaxation of X
=
X
Z, which is referred to as the self-expressiveness of X with Z representing the similarity between data points. Because the LogDet function is not convex in Z, we resort to ALM technique to solve (6), by rewriting (6) as follows:(7)
m
i
n
Z
LogDet
⁡
I
+
Z
T
Z
+
ρ
X
-
X
W
F
2
s.t.
Z
=
W
.We turn to the minimizing of the following augmented Lagrangian function:(8)
L
Y
,
Z
,
W
,
β
=
LogDet
⁡
I
+
Z
T
Z
+
ρ
X
-
X
W
F
2
+
β
2
Z
-
W
F
2
+
Tr
⁡
Y
T
Z
-
W
,where β
>
0 is a penalty parameter and Y is the Lagrangian dual variable. With a sufficiently large β, the objective function converges to objective function in (6). This can be solved by updating Z, W, and Y alternatively while fixing the other variables. Specifically, assume that at the kth iteration we have obtained Z
k
,
W
k, and Y
k; then, for the (
k
+
1
)th iteration, optimization problem (8) can be updated via the following four steps.Step 1.
ComputeW
k
+
1. Fix Z
k and Y
k and then calculate W
k
+
1:(9)
W
k
+
1
=
arg
⁡
min
W
⁡
ρ
X
-
X
W
F
2
+
β
k
2
Z
k
-
W
-
1
β
k
Y
k
F
2
,which has a closed-form solution:(10)
W
k
+
1
=
β
k
I
+
2
ρ
X
T
X
-
1
2
ρ
X
T
X
+
Y
k
+
β
k
Z
k
.Step 2.
ComputeZ
k
+
1. Fix W
k
+
1 and Y
k and minimize L
(
Y
k
,
Z
,
W
k
+
1
,
β
k
) as follows:(11)
Z
k
+
1
=
arg
⁡
min
Z
⁡
L
Y
k
,
Z
,
W
k
+
1
,
β
k
=
arg
⁡
min
Z
⁡
LogDet
⁡
I
+
Z
T
Z
+
β
k
2
Z
-
W
k
+
1
-
1
β
k
Y
k
F
2
.This can be converted to a scalar minimization problem due to the following theorem. As we notice, this can also be rewritten as a special case of the problem in a recent work [25].Theorem 2.
For unitarily invariant functionF
(
Z
)
=
f
∘
σ
(
Z
), assuming SVD of A
∈
R
m
×
n is A
=
U
Σ
A
V
T, Σ
A
=
diag
⁡
(
{
σ
i
,
A
}
i
=
1
m
i
n
(
m
,
n
)
), the optimal solution to the problem(12)
min
Z
⁡
F
Z
+
β
2
Z
-
A
F
2is Z
∗
=
U
Σ
Z
∗
V
T, with Σ
Z
∗
=
diag
⁡
(
{
σ
i
∗
}
i
=
1
m
i
n
(
m
,
n
)
) obtained by solving scalar minimization problems(13)
σ
i
∗
=
arg
⁡
min
σ
i
⁡
f
σ
i
+
β
2
σ
i
-
σ
i
,
A
2
,
i
=
1
,
…
,
min
⁡
m
,
n
.Proof.
LetA
=
U
Σ
A
V
T be SVD of A; then Σ
A
=
U
T
A
V. Denoting X
=
U
T
Z
V which has exactly the same singular values as Z, that is, Σ
X
=
Σ
Z, we have (14)
F
Z
+
β
2
Z
-
A
F
2
(15)
=
F
X
+
β
2
X
-
Σ
A
F
2
(16)
=
F
Σ
X
+
β
2
X
-
Σ
A
F
2
(17)
=
F
Σ
X
+
β
2
X
F
2
+
Σ
A
F
2
-
2
X
,
Σ
A
(18)
≥
F
Σ
X
+
β
2
Σ
X
F
2
+
Σ
A
F
2
-
2
Σ
X
,
Σ
A
(19)
=
F
Σ
X
+
β
2
Σ
X
-
Σ
A
F
2
(20)
=
F
Σ
Z
+
β
2
Σ
Z
-
Σ
A
F
2
(21)
=
∑
i
f
σ
i
+
β
2
σ
i
-
σ
i
,
A
2
(22)
≥
∑
i
f
σ
i
∗
+
β
2
σ
i
∗
-
σ
i
,
A
2
.In the above, (15) holds because the Frobenius norm is unitary invariant; (16) holds because F
(
Z
) is unitary invariant; (17) is true by von Neumann’s inequality; and (20) holds as Σ
X
=
Σ
Z. The inequality between (15) and (19) can also be obtained by the Hoffman-Wielandt inequality. Therefore, (20) is a lower bound of (14), where Σ
Z
∗ is obtained by minimizing (20). Note that the equality in (18) is attained if X
=
Σ
X. Because Σ
Z
=
Σ
X
=
X
=
U
T
Z
V, the SVD of Z is Z
=
U
Σ
Z
V
T, which is the minimizer of problem (12). Hence the proof is completed.The first-order optimality condition is that the gradient of (13) with respect to each singular value should vanish. Thus, for subproblem (11), we have(23)
2
σ
i
1
+
σ
i
2
+
β
k
σ
i
-
Σ
i
k
=
0
,
s.t.
σ
i
≥
0
,
for
i
=
1
,
…
,
n
,where SVD of W
k
+
1
-
(
1
/
β
k
)
Y
k is U
diag
⁡
(
{
Σ
i
k
}
i
=
1
n
)
V
T. The above equation is cubic and gives three roots. In addition, we need to enforce the nonnegativity of σ
i. It is easily seen that there exists at least one nonnegative root. And there is a unique minimizer σ
i
∗
∈
[
0
,
Σ
i
k
) if β
k
>
1
/
4. Finally, we obtain the update of Z variable with Z
k
+
1
=
U
diag
⁡
(
σ
1
k
∗
,
…
,
σ
n
∗
)
V
T.Step 3.
ComputeY
k
+
1. Fix Z
k
+
1 and W
k
+
1, and then we calculate Y
k
+
1 as follows:(24)
Y
k
+
1
=
Y
k
+
β
k
Z
k
+
1
-
W
k
+
1
.Step 4.
Updateβ
k
+
1 as β
k
+
1
=
γ
β
k. The complete procedure is summarized in Algorithm 1.
Problem (6) is nonconvex. It is difficult to give a rigorous mathematical argument for convergence to (local) optimum. We will provide a theoretical proof that our algorithm converges to an accumulation point and this accumulation point is a stationary point. Our empirical experiments confirm the convergence of the proposed method on the benchmark datasets. The experimental results are promising, despite the fact that the solution obtained by the proposed optimization method may be a local optimum.Algorithm 1:LogDet Rank Minimization.
Input: data matrix X, parameters ρ
>
0, γ
>
1, and β
0
>
0.
Initialize:  Z
=
I
∈
R
n
×
n, Y
=
0.
Repeat
(1) Update W as:
W
k
+
1
=
β
k
I
+
2
ρ
X
T
X
-
1
2
ρ
X
T
X
+
Y
k
+
β
k
Z
k
+
1.
(2) Solve Z using (11) and (23).
(3) Update the augmented multiplier Y and the augmented Lagrange multiplier β:
Y
k
+
1
=
Y
k
+
β
k
Z
k
+
1
-
W
k
+
1,
β
k
+
1
=
γ
β
k.
Until stopping criterion is satisfied.
Return  Z
∗
=
Z
k
+
1.


### 3.2. Affinity Graph Matrix Construction

Now we will construct an affinity matrixW for subspace clustering. Optimal Z
∗ may not accurately describe the relationship between samples if the data is severely corrupted. Therefore, in general, it is not a good idea to construct W by directly using Z
∗. In the spirit of [3, 12], we construct an affinity matrix in the following way.Assuming the skinny SVD ofZ
∗ is U
∗
Σ
∗
(
V
∗
)
T, we define M
=
U
∗
(
Σ
∗
)
1
/
2 and N
=
(
Σ
∗
)
1
/
2
(
V
∗
)
T. Based on the weighted eigenvector matrix M or N, we construct an affinity matrix W as follows:(25)
W
i
j
=
m
i
T
m
j
m
i
2
m
j
2
2
α
or
W
i
j
=
n
i
T
n
j
n
i
2
n
j
2
2
α
,where m
i (n
i) and m
j (n
j) represent the ith and jth columns (rows) of M (N), respectively, and parameter α
∈
N tunes the sharpness of the affinity between two points, with α
>
1 helping in separating the clusters. When α increases, while the between-cluster separability can be increased, the intracluster cohesiveness would nevertheless be degraded. Thus, a suitable α needs to balance within-cluster cohesiveness and between-cluster separability. In this paper, we set α to be 2. Then we have the same postprocessing as LRR. (For LRR, we use (12) in [3] rather than (3) to construct W. We also confirmed with an author of [3] that the power 2 of (12) is a typo and it should be 4.) As U
∗ or V
∗ spans the principal directions of Z
∗, we employ the angle information or powered correlation coefficients of the examples, because their lengths may be affected significantly by the noise or outliers in the data.Now using the resultant affinity matrix, we can apply spectral clustering algorithm to do segmentation. In this paper, we simply perform NCuts [18] on W. The proposed subspace clustering procedure is summarized in Algorithm 2.Algorithm 2:The SCLD Algorithm.
Input: data matrix X, number of subspaces k, parameters ρ
>
0, γ
>
1, and β
0
>
0.
(1) ObtainZ
∗ from Algorithm 1.
(2) Compute the skinny SVDZ
∗
=
U
∗
Σ
∗
(
V
∗
)
T.
(3) CalculateM
=
U
∗
(
Σ
∗
)
1
/
2 or N
=
(
Σ
∗
)
1
/
2
(
V
∗
)
T.
(4)  Construct the affinity graph matrixW by (25).
(5) ApplyW to perform NCuts.


## 3.1. LogDet Rank Minimization

We useLogDet
⁡
(
I
+
Z
T
Z
) as a surrogate of the rank function of Z. It is obvious that LogDet
⁡
(
I
+
Z
T
Z
)
=
∑
i
=
1
n
‍
log
⁡
(
1
+
σ
i
2
(
Z
)
). Because it can be easily verified that l
o
g
(
1
+
σ
i
2
(
Z
)
)
≤
σ
i
(
Z
) for any σ
i
(
Z
)
≥
0, we always have LogDet
⁡
(
I
+
Z
T
Z
)
≤
Z
∗; particularly, if there are large nonzero singular values, the LogDet function will be much smaller than the nuclear norm since l
o
g
(
1
+
σ
i
2
(
Z
)
)
≪
σ
i
(
Z
) for a large σ
i
(
Z
)
>
1. It is noted that, for small nonzero singular values, their contribution to the LogDet function will be significantly reduced compared to the nuclear norm. Because small nonzero singular values are often regarded as being from noise in the data, the LogDet function reduces noise effect more compared to the nuclear norm.It is worthwhile to note that a similar functionLogDet
⁡
(
X
+
δ
I
) was proposed in [24] to approximate rank and iterative linearization was used to find a local minimum. However, δ is a very small constant (e.g., 1
0
-
6), which leads to biased approximation for small singular values.This LogDet function is differentiable with respect to the singular values by Theorem1, and even though it is nonconvex, its minimization is rather simple by using our optimization method. To explain its minimization, we consider its specific application to subspace clustering. By employing the above LogDet function, we simply formulate the subspace clustering into the following unconstrained nonconvex minimization problem:(6)
min
Z
⁡
LogDet
⁡
I
+
Z
T
Z
+
ρ
X
-
X
Z
F
2
,where I
∈
R
n
×
n is the identity matrix. The first term of (6) is to minimize the rank of Z, while the second is a relaxation of X
=
X
Z, which is referred to as the self-expressiveness of X with Z representing the similarity between data points. Because the LogDet function is not convex in Z, we resort to ALM technique to solve (6), by rewriting (6) as follows:(7)
m
i
n
Z
LogDet
⁡
I
+
Z
T
Z
+
ρ
X
-
X
W
F
2
s.t.
Z
=
W
.We turn to the minimizing of the following augmented Lagrangian function:(8)
L
Y
,
Z
,
W
,
β
=
LogDet
⁡
I
+
Z
T
Z
+
ρ
X
-
X
W
F
2
+
β
2
Z
-
W
F
2
+
Tr
⁡
Y
T
Z
-
W
,where β
>
0 is a penalty parameter and Y is the Lagrangian dual variable. With a sufficiently large β, the objective function converges to objective function in (6). This can be solved by updating Z, W, and Y alternatively while fixing the other variables. Specifically, assume that at the kth iteration we have obtained Z
k
,
W
k, and Y
k; then, for the (
k
+
1
)th iteration, optimization problem (8) can be updated via the following four steps.Step 1.
ComputeW
k
+
1. Fix Z
k and Y
k and then calculate W
k
+
1:(9)
W
k
+
1
=
arg
⁡
min
W
⁡
ρ
X
-
X
W
F
2
+
β
k
2
Z
k
-
W
-
1
β
k
Y
k
F
2
,which has a closed-form solution:(10)
W
k
+
1
=
β
k
I
+
2
ρ
X
T
X
-
1
2
ρ
X
T
X
+
Y
k
+
β
k
Z
k
.Step 2.
ComputeZ
k
+
1. Fix W
k
+
1 and Y
k and minimize L
(
Y
k
,
Z
,
W
k
+
1
,
β
k
) as follows:(11)
Z
k
+
1
=
arg
⁡
min
Z
⁡
L
Y
k
,
Z
,
W
k
+
1
,
β
k
=
arg
⁡
min
Z
⁡
LogDet
⁡
I
+
Z
T
Z
+
β
k
2
Z
-
W
k
+
1
-
1
β
k
Y
k
F
2
.This can be converted to a scalar minimization problem due to the following theorem. As we notice, this can also be rewritten as a special case of the problem in a recent work [25].Theorem 2.
For unitarily invariant functionF
(
Z
)
=
f
∘
σ
(
Z
), assuming SVD of A
∈
R
m
×
n is A
=
U
Σ
A
V
T, Σ
A
=
diag
⁡
(
{
σ
i
,
A
}
i
=
1
m
i
n
(
m
,
n
)
), the optimal solution to the problem(12)
min
Z
⁡
F
Z
+
β
2
Z
-
A
F
2is Z
∗
=
U
Σ
Z
∗
V
T, with Σ
Z
∗
=
diag
⁡
(
{
σ
i
∗
}
i
=
1
m
i
n
(
m
,
n
)
) obtained by solving scalar minimization problems(13)
σ
i
∗
=
arg
⁡
min
σ
i
⁡
f
σ
i
+
β
2
σ
i
-
σ
i
,
A
2
,
i
=
1
,
…
,
min
⁡
m
,
n
.Proof.
LetA
=
U
Σ
A
V
T be SVD of A; then Σ
A
=
U
T
A
V. Denoting X
=
U
T
Z
V which has exactly the same singular values as Z, that is, Σ
X
=
Σ
Z, we have (14)
F
Z
+
β
2
Z
-
A
F
2
(15)
=
F
X
+
β
2
X
-
Σ
A
F
2
(16)
=
F
Σ
X
+
β
2
X
-
Σ
A
F
2
(17)
=
F
Σ
X
+
β
2
X
F
2
+
Σ
A
F
2
-
2
X
,
Σ
A
(18)
≥
F
Σ
X
+
β
2
Σ
X
F
2
+
Σ
A
F
2
-
2
Σ
X
,
Σ
A
(19)
=
F
Σ
X
+
β
2
Σ
X
-
Σ
A
F
2
(20)
=
F
Σ
Z
+
β
2
Σ
Z
-
Σ
A
F
2
(21)
=
∑
i
f
σ
i
+
β
2
σ
i
-
σ
i
,
A
2
(22)
≥
∑
i
f
σ
i
∗
+
β
2
σ
i
∗
-
σ
i
,
A
2
.In the above, (15) holds because the Frobenius norm is unitary invariant; (16) holds because F
(
Z
) is unitary invariant; (17) is true by von Neumann’s inequality; and (20) holds as Σ
X
=
Σ
Z. The inequality between (15) and (19) can also be obtained by the Hoffman-Wielandt inequality. Therefore, (20) is a lower bound of (14), where Σ
Z
∗ is obtained by minimizing (20). Note that the equality in (18) is attained if X
=
Σ
X. Because Σ
Z
=
Σ
X
=
X
=
U
T
Z
V, the SVD of Z is Z
=
U
Σ
Z
V
T, which is the minimizer of problem (12). Hence the proof is completed.The first-order optimality condition is that the gradient of (13) with respect to each singular value should vanish. Thus, for subproblem (11), we have(23)
2
σ
i
1
+
σ
i
2
+
β
k
σ
i
-
Σ
i
k
=
0
,
s.t.
σ
i
≥
0
,
for
i
=
1
,
…
,
n
,where SVD of W
k
+
1
-
(
1
/
β
k
)
Y
k is U
diag
⁡
(
{
Σ
i
k
}
i
=
1
n
)
V
T. The above equation is cubic and gives three roots. In addition, we need to enforce the nonnegativity of σ
i. It is easily seen that there exists at least one nonnegative root. And there is a unique minimizer σ
i
∗
∈
[
0
,
Σ
i
k
) if β
k
>
1
/
4. Finally, we obtain the update of Z variable with Z
k
+
1
=
U
diag
⁡
(
σ
1
k
∗
,
…
,
σ
n
∗
)
V
T.Step 3.
ComputeY
k
+
1. Fix Z
k
+
1 and W
k
+
1, and then we calculate Y
k
+
1 as follows:(24)
Y
k
+
1
=
Y
k
+
β
k
Z
k
+
1
-
W
k
+
1
.Step 4.
Updateβ
k
+
1 as β
k
+
1
=
γ
β
k. The complete procedure is summarized in Algorithm 1.
Problem (6) is nonconvex. It is difficult to give a rigorous mathematical argument for convergence to (local) optimum. We will provide a theoretical proof that our algorithm converges to an accumulation point and this accumulation point is a stationary point. Our empirical experiments confirm the convergence of the proposed method on the benchmark datasets. The experimental results are promising, despite the fact that the solution obtained by the proposed optimization method may be a local optimum.Algorithm 1:LogDet Rank Minimization.
Input: data matrix X, parameters ρ
>
0, γ
>
1, and β
0
>
0.
Initialize:  Z
=
I
∈
R
n
×
n, Y
=
0.
Repeat
(1) Update W as:
W
k
+
1
=
β
k
I
+
2
ρ
X
T
X
-
1
2
ρ
X
T
X
+
Y
k
+
β
k
Z
k
+
1.
(2) Solve Z using (11) and (23).
(3) Update the augmented multiplier Y and the augmented Lagrange multiplier β:
Y
k
+
1
=
Y
k
+
β
k
Z
k
+
1
-
W
k
+
1,
β
k
+
1
=
γ
β
k.
Until stopping criterion is satisfied.
Return  Z
∗
=
Z
k
+
1.


## 3.2. Affinity Graph Matrix Construction

Now we will construct an affinity matrixW for subspace clustering. Optimal Z
∗ may not accurately describe the relationship between samples if the data is severely corrupted. Therefore, in general, it is not a good idea to construct W by directly using Z
∗. In the spirit of [3, 12], we construct an affinity matrix in the following way.Assuming the skinny SVD ofZ
∗ is U
∗
Σ
∗
(
V
∗
)
T, we define M
=
U
∗
(
Σ
∗
)
1
/
2 and N
=
(
Σ
∗
)
1
/
2
(
V
∗
)
T. Based on the weighted eigenvector matrix M or N, we construct an affinity matrix W as follows:(25)
W
i
j
=
m
i
T
m
j
m
i
2
m
j
2
2
α
or
W
i
j
=
n
i
T
n
j
n
i
2
n
j
2
2
α
,where m
i (n
i) and m
j (n
j) represent the ith and jth columns (rows) of M (N), respectively, and parameter α
∈
N tunes the sharpness of the affinity between two points, with α
>
1 helping in separating the clusters. When α increases, while the between-cluster separability can be increased, the intracluster cohesiveness would nevertheless be degraded. Thus, a suitable α needs to balance within-cluster cohesiveness and between-cluster separability. In this paper, we set α to be 2. Then we have the same postprocessing as LRR. (For LRR, we use (12) in [3] rather than (3) to construct W. We also confirmed with an author of [3] that the power 2 of (12) is a typo and it should be 4.) As U
∗ or V
∗ spans the principal directions of Z
∗, we employ the angle information or powered correlation coefficients of the examples, because their lengths may be affected significantly by the noise or outliers in the data.Now using the resultant affinity matrix, we can apply spectral clustering algorithm to do segmentation. In this paper, we simply perform NCuts [18] on W. The proposed subspace clustering procedure is summarized in Algorithm 2.Algorithm 2:The SCLD Algorithm.
Input: data matrix X, number of subspaces k, parameters ρ
>
0, γ
>
1, and β
0
>
0.
(1) ObtainZ
∗ from Algorithm 1.
(2) Compute the skinny SVDZ
∗
=
U
∗
Σ
∗
(
V
∗
)
T.
(3) CalculateM
=
U
∗
(
Σ
∗
)
1
/
2 or N
=
(
Σ
∗
)
1
/
2
(
V
∗
)
T.
(4)  Construct the affinity graph matrixW by (25).
(5) ApplyW to perform NCuts.


## 4. Convergence Analysis

In this section, we give the convergence analysis for Algorithm1. We will show that our optimization algorithm attains at least one stationary point of problem (7). We first rewrite the objective function of (7) as (26)
G
Z
,
W
=
F
Z
+
ρ
X
-
X
W
F
2
s.t.
Z
=
W
,
(27)
H
Z
,
W
,
Y
=
G
Z
,
W
+
Z
-
W
,
Y
,
(28)
L
Z
,
W
,
Y
,
β
=
H
Z
,
W
,
Y
+
β
2
Z
-
W
F
2
.Lemma 3.
The sequence{
Y
k
} is bounded.Proof.
To minimizeZ at step k
+
1, the optimal Z
k
+
1 needs to satisfy the first-order optimality condition (29)
∇
Z
L
Z
,
W
k
+
1
,
Y
k
,
β
k
Z
k
+
1
=
∇
Z
F
Z
Z
k
+
1
+
β
k
Z
k
+
1
+
1
β
k
Y
k
-
W
k
+
1
=
0
.Note that the updating rule for Y is(30)
Y
k
+
1
=
Y
k
+
β
k
Z
k
+
1
-
W
k
+
1
;thus ∇
Z
F
Z
Z
k
+
1
+
Y
k
+
1
=
0. We know from (5) that(31)
∇
Z
F
Z
Z
k
+
1
=
U
diag
⁡
2
σ
1
1
+
σ
1
2
,
…
,
2
σ
n
1
+
σ
n
2
V
T
,and 0
≤
2
σ
i
/
(
1
+
σ
i
2
)
≤
1, so ∇
Z
F
Z
Z
k
+
1 is bounded. Then it is seen that Y
k
+
1; that is, {
Y
k
} is bounded.Lemma 4.
{
W
k
} and {
Z
k
} are bounded if ∑
‍
(
β
k
+
1
/
β
k
2
)
<
∞ and ∑
‍
(
1
/
β
k
)
<
∞.Proof.
Consider(32)
L
Z
k
,
W
k
,
Y
k
,
β
k
=
L
Z
k
,
W
k
,
Y
k
-
1
,
β
k
-
1
+
β
k
-
β
k
-
1
2
Z
k
-
W
k
F
2
+
Tr
⁡
Y
k
-
Y
k
-
1
Z
k
-
W
k
=
L
Z
k
,
W
k
,
Y
k
-
1
,
β
k
-
1
+
β
k
+
β
k
-
1
2
β
k
-
1
2
Y
k
-
Y
k
-
1
F
2
.
Thus,(33)
L
Z
k
+
1
,
W
k
+
1
,
Y
k
,
β
k
≤
L
Z
k
,
W
k
+
1
,
Y
k
,
β
k
≤
L
Z
k
,
W
k
,
Y
k
,
β
k
≤
L
Z
k
,
W
k
,
Y
k
-
1
,
β
k
-
1
+
β
k
+
β
k
-
1
2
β
k
-
1
2
Y
k
-
Y
k
-
1
F
2
≤
⋯
≤
L
Z
1
,
W
1
,
Y
0
,
β
0
+
∑
i
=
1
k
β
i
+
β
i
-
1
2
β
i
-
1
2
Y
i
-
Y
i
-
1
F
2
.Since the second term in the above inequality is finite, L
Z
k
+
1
,
W
k
+
1
,
Y
k
,
β
k is bounded. We can rewrite L
Z
k
+
1
,
W
k
+
1
,
Y
k
,
β
k as(34)
L
Z
k
+
1
,
W
k
+
1
,
Y
k
,
β
k
+
1
2
β
k
Y
k
F
2
=
F
Z
k
+
1
+
ρ
X
-
X
W
k
+
1
F
2
+
β
k
2
Z
k
+
1
-
W
k
+
1
+
1
β
k
Y
k
F
2
.Because L
(
Z
k
+
1
,
W
k
+
1
,
Y
k
,
β
k
) and (
1
/
β
k
)
Y
k
F
2 are bounded and each term on the right hand side of (34) is nonnegative, each term will be bounded. F
(
Z
k
+
1
)
=
∑
i
‍
l
o
g
(
1
+
σ
i
2
(
Z
k
+
1
)
) being bounded implies that all singular values of Z
k
+
1 are bounded and Z
k
+
1 is bounded. Since (1
/
β
k)(
Y
k
+
1
-
Y
k
)
=
Z
k
+
1
-
W
k
+
1, clearly we have bounded W
k. Therefore {
W
k
} and {
Z
k
} are bounded.Theorem 5.
{
Y
k
,
W
k
,
Z
k
} has at least one accumulation point {
Y
∗
,
W
∗
,
Z
∗
}, and {
W
∗
,
Z
∗
} is a stationary point of optimization problem (7) with the assumption that l
i
m
k
→
∞
β
k
-
1
(
Z
k
-
Z
k
-
1
)
→
0.Proof.
{
Y
k
,
W
k
,
Z
k
} is a bounded sequence; hence, by the Bolzano-Weierstrass theorem, there must be at least one accumulation point, which is denoted by {
Y
∗
,
W
∗
,
Z
∗
}. Without loss of generality, we assume that {
Y
k
,
W
k
,
Z
k
} itself converges to {
Y
∗
,
W
∗
,
Z
∗
}. Next, we prove that this accumulation point is a stationary point of problem (26). As Y
k
=
Y
k
-
1
+
β
k
-
1
(
Z
k
-
W
k
), we have Z
k
-
W
k
=
(
1
/
β
k
-
1
)
(
Y
k
-
Y
k
-
1
). Because β
k
-
1
→
∞ and {
Y
k
} is bounded, we get Z
k
-
W
k
→
0; that is, Z
∗
=
W
∗. By first-order optimality condition and the definition of Z
k, we have ∇
Z
F
(
Z
)
|
Z
k
+
Y
k
-
1
+
β
k
-
1
(
Z
k
-
W
k
)
=
∇
Z
F
Z
|
Z
k
+
Y
k
=
0. Letting k
→
∞, we get ∇
Z
F
Z
|
Z
∗
+
Y
∗
=
0. At the kth step, W
k satisfies (
2
ρ
X
T
X
+
β
k
-
1
I
)
W
k
=
2
ρ
X
T
X
+
β
k
-
1
Z
k
-
1
+
Y
k
-
1; that is, 2
ρ
X
T
X
W
k
-
I
=
β
k
-
1
Z
k
-
1
-
β
k
-
1
W
k
+
Y
k
-
1
=
β
k
-
1
Z
k
-
W
k
+
β
k
-
1
(
Z
k
-
1
-
Z
k
)
+
Y
k
-
1
=
β
k
-
1
(
Z
k
-
1
-
Z
k
)
+
Y
k. With the assumption that β
k
-
1
(
Z
k
-
Z
k
-
1
)
→
0 [26], we get 2
ρ
X
T
X
(
W
∗
-
I
)
=
Y
∗.
Now we can see that{
Y
∗
,
W
∗
,
Z
∗
} satisfies the KKT conditions of L
(
W
,
Z
,
Y
) and thus {
W
∗
,
Z
∗
} is a stationary point of (7).


## 5. Experiments and Analysis

In this section, we conduct experiments on the subspace clustering task with both synthetic and real data.


### 5.1. Experiments with Synthetic Data

We construct 5 independent subspaces whose bases{
U
i
}
i
=
1
5 are generated by a random rotation matrix R through U
i
+
1
=
R
U
i, 1
≤
i
≤
4, where U
1
∈
R
100
×
4 is a random orthogonal matrix [2]. We sample 20 data vectors from each subspace by X
j
=
U
j
T
j, 1
≤
j
≤
5, where T
j is a 4
×
20 i.i.d. N
(
0,1
) matrix. Some data vectors are randomly chosen to corrupt; for example, for a data vector x, it is corrupted by adding Gaussian noise with zero mean and variance 0.2
x. We then use SCLD to segment the data into 5 clusters. Subspace clustering error rate defined as #
o
f
m
i
s
c
l
a
s
s
i
f
i
e
d
p
o
i
n
t
s
/
t
o
t
a
l
#
o
f
p
o
i
n
t
s is used to assess the performance. We report the clustering error rate (averaged from 30 trials) with different corruption levels in Figure 1. Without any corruption, SCLD can cluster all data points correctly.Figure 1
The clustering error rate with different percentage of corruption on synthetic data. The parameterρ is tuned to obtain the best performance.


### 5.2. Experiments with Real Data

In this section, we evaluate the effectiveness and robustness of SCLD on benchmark datasets, Extended Yale B (EYaleB) [27, 28] and Hopkins 155 [29]. We compare the proposed method SCLD with several state-of-the-art subspace clustering algorithms: LRR [3], SSC [10], LRSC [4, 30], and local subspace affinity (LSA) [13]. For these methods, we use the parameters given by the respective authors. For our method, we also tune ρ to obtain the best performance. Generally, ρ should be relatively large if the data are slightly corrupted. β and γ have little influence on the clustering results, so we just set β
0
=
0.3 to ensure the uniqueness of minimizer and use γ
=
1.1 empirically. Other parameters are shown in Table 1. The experiments are conducted on Windows 7 with 16 GM memory and Intel Core i5-2300 CPU.Table 1
Parameter settings of different algorithms.
Method
Face clustering
Motion segmentation
Scenario 1
Scenario 2
LRR
λ
=
0.18
λ
=
4
LSA
K
=
3, d
=
5
K
=
8, d
=
5
SSC
λ
e
=
8
μ
e
λ
e
=
20
μ
e
λ
z
=
800
μ
z
LRSC
τ
=
0.4, α
=
0.045
τ
=
0.045, α
=
0.045
τ
=
420, α
=
3000, or α
=
5000
SCLD
ρ
=
0.08
ρ
=
0.03
ρ
=
55


#### 5.2.1. Face Clustering

Face clustering is to cluster a set of face images from multiple individuals in a hope to reveal the identity of these individuals. EYaleB Database includes 2414 frontal images of 38 individuals. For each individual, the images are taken under 64 lighting conditions and can be described by a low-dimensional subspace [31]. The images are resized to 48 × 42 pixels and each vectorized image is regarded as a data point. Figure 2 shows some example images from the database.Figure 2
Sample images from the Extended Yale B Database.(1) First Experiment Scenario. As done in [2], we test the algorithms on the first 10 classes of EYaleB, which consists of 640 frontal face images. More than half of the images are corrupted by shadow and noise. We use this heavily corrupted data to test the effectiveness of our method. As shown in Table 2, SCLD significantly enhances the performance. Specifically, it improves the clustering accuracy by at least 17
% when compared to the other algorithms. Since the only difference between our approach and LRR is rank approximation, this improvement is due to LogDet.Table 2
Clustering error rate on the first 10 classes of EYaleB.
Method
LRR
SSC
LSA
LRSC
SCLD
Error rate (%)
20.94
35
59.52
35.78
3.59(2) Second Experiment Scenario. For a fair comparison, we have followed the experimental setup of [10]. We divide the 38 subjects into four groups: subjects 1 to 10, 11 to 20, 21 to 30, and 31 to 38. We consider all choices of n
∈
{
2,3
,
5,8
,
10
} subjects for the first three groups. For the last group, we consider all choices of n
∈
{
2,3
,
5,8
}. We implement our subspace clustering algorithm on each set of n subjects. For all experiments, the stopping criterion for Z is triggered by a relative difference of 1
0
-
5 between two successive iterations or by a maximum of 100 iterations.The results are presented in Table3. For other methods, we cited the results from Table 5 of [10]. SCLD consistently has low clustering error rates and is more stable than the other methods whose error rates increase drastically as the number of subjects increases to 8 and 10. As shown in Figure 2, there are many sparse within-sample outliers in the face images, for example, shadows. Although LRR uses a regularization term to count for corruptions, the regularization term does not appear to be well suited to EYaleB. LSA has inferior performance possibly because it does not explicitly exploit the low-rank structure of the data.Table 3
Clustering error rates (%) on EYaleB.
Method
LRR
SSC
LSA
LRSC
SCLD
2 subjects
Mean
2.54
1.86
32.80
5.32
2.79
Median
0.78
0.00
47.66
4.69
0.78
3 subjects
Mean
4.21
3.10
52.29
8.47
3.72
Median
2.60
1.04
50.00
7.81
1.56
5 subjects
Mean
6.90
4.31
58.02
12.24
4.83
Median
5.63
2.50
56.87
11.25
2.50
8 subjects
Mean
14.34
5.85
59.19
23.72
5.45
Median
10.06
4.49
58.59
28.03
3.52
10 subjects
Mean
22.92
10.94
60.42
30.36
6.25
Median
23.59
5.63
57.50
28.75
4.84(3) Third Experiment Scenario. In this section, we compare SCLD with other algorithms with RPCA [32] as a preprocessing step. In practice, we do not know the clustering of the data beforehand and hence we apply RPCA to the collection of all data points for each trial prior to clustering. As shown in Table 4, SCLD is still superior to other methods though they apply RPCA to deal with sparse outlying entries. Compared to Table 3, only the clustering error rates of LRSC reduced in some cases. We can conclude that applying RPCA to all data points simultaneously is not effective in improving clustering performance. This is due to the fact that RPCA seeks a common low-rank subspace, which will decrease the principal angles between subspaces and decrease the distance between data points in different subjects [10].Table 4
Clustering error rates (%) on EYaleB after applying RPCA simultaneously to all the data in each trial.
Method
LRR
SSC
LSA
LRSC
SCLD
2 subjects
Mean
5.72
2.09
32.53
5.67
2.79
Median
3.91
0.78
47.66
4.69
0.78
3 subjects
Mean
10.01
3.77
53.02
8.72
3.72
Median
9.38
2.60
51.04
8.33
1.56
5 subjects
Mean
15.33
6.79
58.76
10.99
4.83
Median
15.94
5.31
56.87
10.94
2.50
8 subjects
Mean
28.67
10.28
62.32
16.14
5.45
Median
31.05
9.57
62.50
14.65
3.52
10 subjects
Mean
32.55
11.46
62.40
21.82
6.25
Median
30.00
11.09
62.50
25.00
4.84


#### 5.2.2. Motion Segmentation

Motion segmentation is to segment the trajectories associated withn different moving objects into different groups according to their motions in a video sequence. Because different motions can be treated as different subspaces, we use the Hopkins 155 Dataset to validate SCLD. This dataset is slightly corrupted as shown in Figure 3. It consists of 155 sequences of two or three motions and 1 sequence of 5 motions; the latter is regarded as outlier. Each sequence is regarded as a separate clustering problem.Figure 3
Example frames from four video sequences of the Hopkins 155 Dataset with traced feature points.The experimental results are reported in Table5. We also used the results in Table 1 of [10]. It can be seen that SCLD produces superior results compared to the other methods. For all 155 sequences, the error rate is as low as 1.79%. If we use all 156 sequences, the overall error rate of our proposed algorithm will be 1.87%. We report the average computation time for every sequence at the bottom of Table 5. The computational cost of LRSC is much lower than the other methods, while LRR, SSC, and SCLD are comparable.Table 5
Segmentation error rate (%) on the Hopkins 155 Dataset (155 sequences).
Method
LRR
SSC
LSA
LRSC
SCLD
2 motions
Mean
2.13
1.52
4.23
3.69
1.31
Median
0.00
0.00
0.56
0.29
0.00
3 motions
Mean
4.03
4.40
7.02
7.69
3.43
Median
1.43
0.56
1.45
3.80
0.56
All
Mean
2.56
2.18
4.86
4.59
1.79
Median
0.00
0.00
0.89
0.60
0.00
Time (sec)
1.30
1.04
3.40
0.16
1.49To testify the influence of parameterρ in our algorithm, we show the clustering error rates of SCLD for different ρ over all 155 sequences in Figure 4. As we can see, when ρ was between 1 and 200, the clustering error varied between 1.79% and 4.67%. This implies that SCLD performs well under a wide range of values of ρ.Figure 4
Changes in clustering error rate when varyingρ.To test the dependence of SCLD on initialization, we apply another two different initializations. First, we use the solutions from LRR as initial guess for SCLD. Second, we just generate some random numbers. We find that we can still get the same results. Actually, it is recommended to use convex relaxation solutions as initialization for nonconvex formulations [33, 34].


## 5.1. Experiments with Synthetic Data

We construct 5 independent subspaces whose bases{
U
i
}
i
=
1
5 are generated by a random rotation matrix R through U
i
+
1
=
R
U
i, 1
≤
i
≤
4, where U
1
∈
R
100
×
4 is a random orthogonal matrix [2]. We sample 20 data vectors from each subspace by X
j
=
U
j
T
j, 1
≤
j
≤
5, where T
j is a 4
×
20 i.i.d. N
(
0,1
) matrix. Some data vectors are randomly chosen to corrupt; for example, for a data vector x, it is corrupted by adding Gaussian noise with zero mean and variance 0.2
x. We then use SCLD to segment the data into 5 clusters. Subspace clustering error rate defined as #
o
f
m
i
s
c
l
a
s
s
i
f
i
e
d
p
o
i
n
t
s
/
t
o
t
a
l
#
o
f
p
o
i
n
t
s is used to assess the performance. We report the clustering error rate (averaged from 30 trials) with different corruption levels in Figure 1. Without any corruption, SCLD can cluster all data points correctly.Figure 1
The clustering error rate with different percentage of corruption on synthetic data. The parameterρ is tuned to obtain the best performance.


## 5.2. Experiments with Real Data

In this section, we evaluate the effectiveness and robustness of SCLD on benchmark datasets, Extended Yale B (EYaleB) [27, 28] and Hopkins 155 [29]. We compare the proposed method SCLD with several state-of-the-art subspace clustering algorithms: LRR [3], SSC [10], LRSC [4, 30], and local subspace affinity (LSA) [13]. For these methods, we use the parameters given by the respective authors. For our method, we also tune ρ to obtain the best performance. Generally, ρ should be relatively large if the data are slightly corrupted. β and γ have little influence on the clustering results, so we just set β
0
=
0.3 to ensure the uniqueness of minimizer and use γ
=
1.1 empirically. Other parameters are shown in Table 1. The experiments are conducted on Windows 7 with 16 GM memory and Intel Core i5-2300 CPU.Table 1
Parameter settings of different algorithms.
Method
Face clustering
Motion segmentation
Scenario 1
Scenario 2
LRR
λ
=
0.18
λ
=
4
LSA
K
=
3, d
=
5
K
=
8, d
=
5
SSC
λ
e
=
8
μ
e
λ
e
=
20
μ
e
λ
z
=
800
μ
z
LRSC
τ
=
0.4, α
=
0.045
τ
=
0.045, α
=
0.045
τ
=
420, α
=
3000, or α
=
5000
SCLD
ρ
=
0.08
ρ
=
0.03
ρ
=
55


### 5.2.1. Face Clustering

Face clustering is to cluster a set of face images from multiple individuals in a hope to reveal the identity of these individuals. EYaleB Database includes 2414 frontal images of 38 individuals. For each individual, the images are taken under 64 lighting conditions and can be described by a low-dimensional subspace [31]. The images are resized to 48 × 42 pixels and each vectorized image is regarded as a data point. Figure 2 shows some example images from the database.Figure 2
Sample images from the Extended Yale B Database.(1) First Experiment Scenario. As done in [2], we test the algorithms on the first 10 classes of EYaleB, which consists of 640 frontal face images. More than half of the images are corrupted by shadow and noise. We use this heavily corrupted data to test the effectiveness of our method. As shown in Table 2, SCLD significantly enhances the performance. Specifically, it improves the clustering accuracy by at least 17
% when compared to the other algorithms. Since the only difference between our approach and LRR is rank approximation, this improvement is due to LogDet.Table 2
Clustering error rate on the first 10 classes of EYaleB.
Method
LRR
SSC
LSA
LRSC
SCLD
Error rate (%)
20.94
35
59.52
35.78
3.59(2) Second Experiment Scenario. For a fair comparison, we have followed the experimental setup of [10]. We divide the 38 subjects into four groups: subjects 1 to 10, 11 to 20, 21 to 30, and 31 to 38. We consider all choices of n
∈
{
2,3
,
5,8
,
10
} subjects for the first three groups. For the last group, we consider all choices of n
∈
{
2,3
,
5,8
}. We implement our subspace clustering algorithm on each set of n subjects. For all experiments, the stopping criterion for Z is triggered by a relative difference of 1
0
-
5 between two successive iterations or by a maximum of 100 iterations.The results are presented in Table3. For other methods, we cited the results from Table 5 of [10]. SCLD consistently has low clustering error rates and is more stable than the other methods whose error rates increase drastically as the number of subjects increases to 8 and 10. As shown in Figure 2, there are many sparse within-sample outliers in the face images, for example, shadows. Although LRR uses a regularization term to count for corruptions, the regularization term does not appear to be well suited to EYaleB. LSA has inferior performance possibly because it does not explicitly exploit the low-rank structure of the data.Table 3
Clustering error rates (%) on EYaleB.
Method
LRR
SSC
LSA
LRSC
SCLD
2 subjects
Mean
2.54
1.86
32.80
5.32
2.79
Median
0.78
0.00
47.66
4.69
0.78
3 subjects
Mean
4.21
3.10
52.29
8.47
3.72
Median
2.60
1.04
50.00
7.81
1.56
5 subjects
Mean
6.90
4.31
58.02
12.24
4.83
Median
5.63
2.50
56.87
11.25
2.50
8 subjects
Mean
14.34
5.85
59.19
23.72
5.45
Median
10.06
4.49
58.59
28.03
3.52
10 subjects
Mean
22.92
10.94
60.42
30.36
6.25
Median
23.59
5.63
57.50
28.75
4.84(3) Third Experiment Scenario. In this section, we compare SCLD with other algorithms with RPCA [32] as a preprocessing step. In practice, we do not know the clustering of the data beforehand and hence we apply RPCA to the collection of all data points for each trial prior to clustering. As shown in Table 4, SCLD is still superior to other methods though they apply RPCA to deal with sparse outlying entries. Compared to Table 3, only the clustering error rates of LRSC reduced in some cases. We can conclude that applying RPCA to all data points simultaneously is not effective in improving clustering performance. This is due to the fact that RPCA seeks a common low-rank subspace, which will decrease the principal angles between subspaces and decrease the distance between data points in different subjects [10].Table 4
Clustering error rates (%) on EYaleB after applying RPCA simultaneously to all the data in each trial.
Method
LRR
SSC
LSA
LRSC
SCLD
2 subjects
Mean
5.72
2.09
32.53
5.67
2.79
Median
3.91
0.78
47.66
4.69
0.78
3 subjects
Mean
10.01
3.77
53.02
8.72
3.72
Median
9.38
2.60
51.04
8.33
1.56
5 subjects
Mean
15.33
6.79
58.76
10.99
4.83
Median
15.94
5.31
56.87
10.94
2.50
8 subjects
Mean
28.67
10.28
62.32
16.14
5.45
Median
31.05
9.57
62.50
14.65
3.52
10 subjects
Mean
32.55
11.46
62.40
21.82
6.25
Median
30.00
11.09
62.50
25.00
4.84


### 5.2.2. Motion Segmentation

Motion segmentation is to segment the trajectories associated withn different moving objects into different groups according to their motions in a video sequence. Because different motions can be treated as different subspaces, we use the Hopkins 155 Dataset to validate SCLD. This dataset is slightly corrupted as shown in Figure 3. It consists of 155 sequences of two or three motions and 1 sequence of 5 motions; the latter is regarded as outlier. Each sequence is regarded as a separate clustering problem.Figure 3
Example frames from four video sequences of the Hopkins 155 Dataset with traced feature points.The experimental results are reported in Table5. We also used the results in Table 1 of [10]. It can be seen that SCLD produces superior results compared to the other methods. For all 155 sequences, the error rate is as low as 1.79%. If we use all 156 sequences, the overall error rate of our proposed algorithm will be 1.87%. We report the average computation time for every sequence at the bottom of Table 5. The computational cost of LRSC is much lower than the other methods, while LRR, SSC, and SCLD are comparable.Table 5
Segmentation error rate (%) on the Hopkins 155 Dataset (155 sequences).
Method
LRR
SSC
LSA
LRSC
SCLD
2 motions
Mean
2.13
1.52
4.23
3.69
1.31
Median
0.00
0.00
0.56
0.29
0.00
3 motions
Mean
4.03
4.40
7.02
7.69
3.43
Median
1.43
0.56
1.45
3.80
0.56
All
Mean
2.56
2.18
4.86
4.59
1.79
Median
0.00
0.00
0.89
0.60
0.00
Time (sec)
1.30
1.04
3.40
0.16
1.49To testify the influence of parameterρ in our algorithm, we show the clustering error rates of SCLD for different ρ over all 155 sequences in Figure 4. As we can see, when ρ was between 1 and 200, the clustering error varied between 1.79% and 4.67%. This implies that SCLD performs well under a wide range of values of ρ.Figure 4
Changes in clustering error rate when varyingρ.To test the dependence of SCLD on initialization, we apply another two different initializations. First, we use the solutions from LRR as initial guess for SCLD. Second, we just generate some random numbers. We find that we can still get the same results. Actually, it is recommended to use convex relaxation solutions as initialization for nonconvex formulations [33, 34].


## 5.2.1. Face Clustering

Face clustering is to cluster a set of face images from multiple individuals in a hope to reveal the identity of these individuals. EYaleB Database includes 2414 frontal images of 38 individuals. For each individual, the images are taken under 64 lighting conditions and can be described by a low-dimensional subspace [31]. The images are resized to 48 × 42 pixels and each vectorized image is regarded as a data point. Figure 2 shows some example images from the database.Figure 2
Sample images from the Extended Yale B Database.(1) First Experiment Scenario. As done in [2], we test the algorithms on the first 10 classes of EYaleB, which consists of 640 frontal face images. More than half of the images are corrupted by shadow and noise. We use this heavily corrupted data to test the effectiveness of our method. As shown in Table 2, SCLD significantly enhances the performance. Specifically, it improves the clustering accuracy by at least 17
% when compared to the other algorithms. Since the only difference between our approach and LRR is rank approximation, this improvement is due to LogDet.Table 2
Clustering error rate on the first 10 classes of EYaleB.
Method
LRR
SSC
LSA
LRSC
SCLD
Error rate (%)
20.94
35
59.52
35.78
3.59(2) Second Experiment Scenario. For a fair comparison, we have followed the experimental setup of [10]. We divide the 38 subjects into four groups: subjects 1 to 10, 11 to 20, 21 to 30, and 31 to 38. We consider all choices of n
∈
{
2,3
,
5,8
,
10
} subjects for the first three groups. For the last group, we consider all choices of n
∈
{
2,3
,
5,8
}. We implement our subspace clustering algorithm on each set of n subjects. For all experiments, the stopping criterion for Z is triggered by a relative difference of 1
0
-
5 between two successive iterations or by a maximum of 100 iterations.The results are presented in Table3. For other methods, we cited the results from Table 5 of [10]. SCLD consistently has low clustering error rates and is more stable than the other methods whose error rates increase drastically as the number of subjects increases to 8 and 10. As shown in Figure 2, there are many sparse within-sample outliers in the face images, for example, shadows. Although LRR uses a regularization term to count for corruptions, the regularization term does not appear to be well suited to EYaleB. LSA has inferior performance possibly because it does not explicitly exploit the low-rank structure of the data.Table 3
Clustering error rates (%) on EYaleB.
Method
LRR
SSC
LSA
LRSC
SCLD
2 subjects
Mean
2.54
1.86
32.80
5.32
2.79
Median
0.78
0.00
47.66
4.69
0.78
3 subjects
Mean
4.21
3.10
52.29
8.47
3.72
Median
2.60
1.04
50.00
7.81
1.56
5 subjects
Mean
6.90
4.31
58.02
12.24
4.83
Median
5.63
2.50
56.87
11.25
2.50
8 subjects
Mean
14.34
5.85
59.19
23.72
5.45
Median
10.06
4.49
58.59
28.03
3.52
10 subjects
Mean
22.92
10.94
60.42
30.36
6.25
Median
23.59
5.63
57.50
28.75
4.84(3) Third Experiment Scenario. In this section, we compare SCLD with other algorithms with RPCA [32] as a preprocessing step. In practice, we do not know the clustering of the data beforehand and hence we apply RPCA to the collection of all data points for each trial prior to clustering. As shown in Table 4, SCLD is still superior to other methods though they apply RPCA to deal with sparse outlying entries. Compared to Table 3, only the clustering error rates of LRSC reduced in some cases. We can conclude that applying RPCA to all data points simultaneously is not effective in improving clustering performance. This is due to the fact that RPCA seeks a common low-rank subspace, which will decrease the principal angles between subspaces and decrease the distance between data points in different subjects [10].Table 4
Clustering error rates (%) on EYaleB after applying RPCA simultaneously to all the data in each trial.
Method
LRR
SSC
LSA
LRSC
SCLD
2 subjects
Mean
5.72
2.09
32.53
5.67
2.79
Median
3.91
0.78
47.66
4.69
0.78
3 subjects
Mean
10.01
3.77
53.02
8.72
3.72
Median
9.38
2.60
51.04
8.33
1.56
5 subjects
Mean
15.33
6.79
58.76
10.99
4.83
Median
15.94
5.31
56.87
10.94
2.50
8 subjects
Mean
28.67
10.28
62.32
16.14
5.45
Median
31.05
9.57
62.50
14.65
3.52
10 subjects
Mean
32.55
11.46
62.40
21.82
6.25
Median
30.00
11.09
62.50
25.00
4.84


## 5.2.2. Motion Segmentation

Motion segmentation is to segment the trajectories associated withn different moving objects into different groups according to their motions in a video sequence. Because different motions can be treated as different subspaces, we use the Hopkins 155 Dataset to validate SCLD. This dataset is slightly corrupted as shown in Figure 3. It consists of 155 sequences of two or three motions and 1 sequence of 5 motions; the latter is regarded as outlier. Each sequence is regarded as a separate clustering problem.Figure 3
Example frames from four video sequences of the Hopkins 155 Dataset with traced feature points.The experimental results are reported in Table5. We also used the results in Table 1 of [10]. It can be seen that SCLD produces superior results compared to the other methods. For all 155 sequences, the error rate is as low as 1.79%. If we use all 156 sequences, the overall error rate of our proposed algorithm will be 1.87%. We report the average computation time for every sequence at the bottom of Table 5. The computational cost of LRSC is much lower than the other methods, while LRR, SSC, and SCLD are comparable.Table 5
Segmentation error rate (%) on the Hopkins 155 Dataset (155 sequences).
Method
LRR
SSC
LSA
LRSC
SCLD
2 motions
Mean
2.13
1.52
4.23
3.69
1.31
Median
0.00
0.00
0.56
0.29
0.00
3 motions
Mean
4.03
4.40
7.02
7.69
3.43
Median
1.43
0.56
1.45
3.80
0.56
All
Mean
2.56
2.18
4.86
4.59
1.79
Median
0.00
0.00
0.89
0.60
0.00
Time (sec)
1.30
1.04
3.40
0.16
1.49To testify the influence of parameterρ in our algorithm, we show the clustering error rates of SCLD for different ρ over all 155 sequences in Figure 4. As we can see, when ρ was between 1 and 200, the clustering error varied between 1.79% and 4.67%. This implies that SCLD performs well under a wide range of values of ρ.Figure 4
Changes in clustering error rate when varyingρ.To test the dependence of SCLD on initialization, we apply another two different initializations. First, we use the solutions from LRR as initial guess for SCLD. Second, we just generate some random numbers. We find that we can still get the same results. Actually, it is recommended to use convex relaxation solutions as initialization for nonconvex formulations [33, 34].


## 6. Conclusion

In this paper we propose using a log-determinant function (LogDet) as a rank approximation to recover the low-rank representation of high-dimensional data. When applied to subspace clustering, the proposed algorithm, called SCLD, exploits both global and local structures of the data through the LogDet rank approximation and angle-based affinity matrix. Consequently, it captures more intrinsic information of the data that benefits subspace clustering. Our extensive experimental results show that it outperforms other low-rank representation algorithms based on the nuclear norm. Therefore LogDet appears to be an effective rank approximation function well suited to subspace clustering applications. Although our model is simple and with no explicit modeling of outliers, it is resilient to various corruptions. Our future research will consider modeling corruptions explicitly.



---

*Source: 824289-2015-07-02.xml*