# Low-Rank Representation for Incomplete Data

Authors: Jiarong Shi; Wei Yang; Longquan Yong; Xiuyun Zheng
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Low-rank matrix recovery (LRMR) has been becoming an increasingly popular technique for analyzing data with missing entries, gross corruptions, and outliers. As a significant component of LRMR, the model of low-rank representation (LRR) seeks the lowest-rank representation among all samples and it is robust for recovering subspace structures. This paper attempts to solve the problem of LRR with partially observed entries. Firstly, we construct a nonconvex minimization by taking the low rankness, robustness, and incompletion into consideration. Then we employ the technique of augmented Lagrange multipliers to solve the proposed program. Finally, experimental results on synthetic and real-world datasets validate the feasibility and effectiveness of the proposed method.


---

## Body

## 1. Introduction

In the community of pattern recognition, machine learning, and computer vision, the investigated datasets usually have intrinsically low-rank structure although they are probably high-dimensional. Low-rank matrix recovery (LRMR) [1–3] is just a type of model which utilizes the crucial low-complexity information to complete missing entries, recover sparse noise, identify outliers, and build an affinity matrix. It also can be regarded as the generalization of compressed sensing from one order to two orders due to the fact that the low rankness of a matrix is equivalent to the sparsity of its singular values. Recently, LRMR has received more and more attentions in the fields of information science and engineering and achieved great success in video background modeling [4, 5], collaborative filtering [6, 7], and subspace clustering [3, 8, 9], to name just a few.Generally, LRMR is mainly composed of three appealing types, that is, matrix completion (MC) [1], robust principal component analysis (RPCA) [2, 4], and low-rank representation (LRR) [3, 8]. Among them, MC aims to complete the missing entries with the aid of the low-rank property and is initially described as an affine rank minimization problem. In the past few years, the affine rank minimization is convexly relaxed into a nuclear norm minimization [10] and it is proven that if the number of sampled entries and singular vectors satisfy some conditions, then most low-rank matrices can be perfectly recovered by solving the aforementioned convex program [1].Classical principal component analysis (PCA) [11] is very effective to small Gaussian noise, but it does not work well in practice when data samples are corrupted by outliers or large sparse noise. For this purpose, several robust variants of PCA have been proposed successively during the past two decades [12, 13]. Since the seminal research work [4], the principal component pursuit (PCP) approach has become a standard for RPCA. This approach minimizes a weighted combination of the nuclear norm and the l
1 norm with linear equality constraints. It is proven that both the low-rank and the sparse components can be recovered exactly with dominant probability under some conditions by solving PCP [4].In subspace clustering, a commonly used assumption is that the data lie in the union of multiple low-rank subspaces and each subspace has sufficient samples compared with its rank. Liu et al. [3] proposed a robust subspace recovery technique via LRR. Any sample in each subspace can be represented as the linear combination of the bases. The low complexity of the linear representation coefficients is very useful in exploiting the low-rank structure. LRR attempts to seek the lowest-rank representation of all data jointly and it is demonstrated that the data contaminated by outliers can be exactly recovered under certain conditions by solving a convex program [8]. If the bases are chosen as the columns of an identity matrix and the l
1 norm is employed to measure the sparsity, then LRR is changed into the PCP of RPCA.For the datasets with missing entries and large sparse corruption, the robust recovery of subspace structures may be a challenging task. The available algorithms to MC are not robust to gross corruption. Moreover, a large quantity of missing values will bring out the degeneration of recovering performance for LRR or RPCA. In this paper, we attempt to address the problem of low-rank subspace recovery in the presence of missing values and sparse noise. Specifically speaking, we present a model of incomplete low-rank representation (ILRR) which is a direct generalization of LRR. The ILRR model can be boiled down to a nonconvex optimization model which minimizes the combination of the nuclear norm and thel
2
,
1-norm. To solve this program, we design an iterative scheme by applying the method of inexact augmented Lagrange multipliers (ALM).The rest of this paper is organized as follows. Section2 briefly reviews preliminaries and related works on LRMR. The model and algorithm for ILRR are presented in Section 3. In Section 4, we discuss the extension of ILRR and its relationship with the existing works. We compare the performance of ILRR with the state-of-the-art algorithms on synthetic data and real-world datasets in Section 5. Finally, Section 6 draws some conclusions.


## 2. Preliminaries and Related Works

This section introduces the relevant preliminary material concerning matrices and representative models of low-rank matrix recovery (LRMR).The choice of matrix norms plays a significant role in LRMR. In the following, we present four important types of matrix norms. For arbitraryX
∈
R
m
×
n, the Frobenius norm of X is expressed by X
F
=
∑
i
=
1
m
∑
j
=
1
n
X
i
j
2, the l
2,1-norm is X
2,1
=
∑
j
=
1
n
∑
i
=
1
m
X
i
j
2, thel
1-norm is X
1
=
∑
i
=
1
m
∑
j
=
1
n
|
X
i
j
|, and the nuclear norm is X
*
=
∑
i
=
1
min
⁡
(
m
,
n
)
σ
i, where X
i
j is the (
i
,
j
)th entry of X and σ
i is the ith largest singular value. Among them, the matrix nuclear norm is the tightest convex relaxation of the rank function, and the l
2,1-norm and the l
1-norm are frequently used to measure the sparsity of a noise matrix.Consider a data matrixD
∈
R
m
×
n stacked by n training samples, where each column of D indicates a sample with the dimensionality of m. Within the field of LRMR, the following three proximal minimization problems [3, 4] are extensively employed:
(1)
min
⁡
X
λ
X
1
+
1
2
X
-
D
F
2
,
min
⁡
X
λ
X
*
+
1
2
X
-
D
F
2
,
min
⁡
X
λ
X
2,1
+
1
2
X
-
D
F
2
,
where λ is a positive constant used to balance the regularization term and the approximation error. For given λ and D, we define three thresholding operators S
λ
(
D
), D
λ
(
D
), and W
λ
(
D
) as follows:
(2)
S
λ
(
D
)
i
j
=
max
⁡
D
i
j
-
λ
,
0
,
D
λ
D
=
U
S
λ
Σ
V
T
,
W
λ
(
D
)
i
j
=
max
⁡
∑
k
=
1
m
D
k
j
2
-
λ
,
0
D
i
j
∑
k
=
1
m
D
k
j
2
,
where U
Σ
V
T is the singular value decomposition (SVD) of D. It is proven that the aforementioned three optimization problems have closed-form solutions denoted by S
λ
(
D
) [4], D
λ
(
D
) [14], and W
λ
(
D
) [8], respectively.We assume thatD is low-rank. Because the degree of freedom of a low-rank matrix is far less than its number of entries, it is possible to recover exactly all missing entries from partially observed entries as long as the number of sampled entries satisfies certain conditions. Formally, the problem of matrix completion (MC) [1] can be formulated as follows:
(3)
min
⁡
X
X
*
s
.
t
.
vviv
X
i
j
=
D
i
j
,
(
i
,
j
)
∈
Ω
,
where Ω
⊂
m
×
[
n
], [
m
]
=
{
1,2
,
…
,
m
}, [
n
]
=
{
1,2
,
…
,
n
}. We define a linear projection operator P
Ω
(
•
)
:
R
m
×
n
→
R
m
×
n as follows:
(4)
P
Ω
(
X
)
i
j
=
X
i
j
,
if
(
i
,
j
)
∈
Ω
0
,
otherwise
.
Hence, the constraints in problem (3) can be rewritten as P
Ω
(
X
)
=
P
Ω
(
D
).PCA obtains the optimal estimate for small additive Gaussian noise but breaks down for large sparse contamination. Here, the data matrixD is assumed to be the superposition of a low-rank matrix A and a sparse noise matrix E. In this situation, robust principal component analysis (RPCA) is very effective to recover both the low-rank and the sparse components by solving a convex program. Mathematically, RPCA can be described as the following nuclear norm minimization [2]:
(5)
min
⁡
A
,
E
A
*
+
λ
E
1
s
.
t
.
vivv
D
=
A
+
E
,
where λ is a positive weighting parameter. Sequentially, RPCA is generalized into a stable version which is simultaneously stable to small perturbations and robust to gross sparse corruption [15].We further assume that the dataset is self-expressive and the representation coefficients matrix is also low-rank. Based on the above two assumptions, the model of low-rank representation (LRR) [3] is expressed as
(6)
min
⁡
Z
,
E
Z
*
+
λ
E
2,1
s
.
t
.
vvv
D
=
D
Z
+
E
,
where Z
∈
R
n
×
n is the coefficient matrix, E is the noise matrix, and λ is a positive trade-off parameter. This model is very effective to detect outliers and the optimal Z is in favor of the robust subspace recovery. In subspace clustering, the affinity matrices can be constructed by the optimal Z to problem (6).Problems (3), (5), and (6) belong to the nuclear norm minimizations. The existing algorithms to the preceding optimizations mainly include the iterative thresholding, the accelerated proximal gradient, the dual approach, and the augmented Lagrange multipliers (ALM) [16]. These algorithms are scalable owing to the adoption of first-order information. Among them, ALM, also called alternating direction method of multipliers (ADMM) [17], is a very popular and effective method to solve the nuclear norm minimizations.


## 3. Model and Algorithm of Incomplete Low-Rank Representation

This section proposes a model of low-rank representation for incomplete data and develops a corresponding iterative scheme for this model.


### 3.1. Model

We consider an incomplete data matrixM
∈
R
m
×
n and denote the sampling index set by Ω. The (
i
,
j
)th entry M
i
j of M is missing if and only if (
i
,
j
)
∉
Ω. For the sake of convenience, we set all missing entries of M to zeros. To recover simultaneously the missing entries and the low-rank subspace structure, we construct an incomplete low-rank representation (ILRR) model:
(7)
min
⁡
Z
,
E
,
D
Z
*
+
λ
E
2,1
s
.
t
.
vviv
D
=
D
Z
+
E
vvvvvv
P
Ω
(
D
)
=
M
,
where λ is a positive constant and D corresponds to the completion argument of M. If there is not any missing entry, that is, Ω
=
[
m
]
×
[
n
], then the above model is equivalent to LRR. In other words, LRR is a special case of ILRR.In order to solve conveniently the nonconvex nuclear norm minimization (7), we introduce two auxiliary matrix variables X
∈
R
m
×
n and J
∈
R
n
×
n. Under this circumstance, the above optimization problem is reformulated as
(8)
min
⁡
Z
,
E
,
D
,
J
,
X
J
*
+
λ
E
2,1
s
.
t
.
vvvvvv
D
=
X
Z
+
E
vvvvvvvv
Z
=
J
,
X
=
D
,
P
Ω
(
D
)
=
M
.
This minimization problem is equivalent to
(9)
min
⁡
Z
,
E
,
D
,
J
,
X
J
*
+
λ
E
2,1
vvvvvvvvvvv
+
μ
2
D
-
X
Z
-
E
F
2
+
Z
-
J
F
2
+
X
-
D
F
2
s
.
t
.
vvvviiv
D
=
X
Z
+
E
vvvvvviivv
Z
=
J
,
X
=
D
,
P
Ω
(
D
)
=
M
,
where the factor μ
>
0. Without considering the constraint P
Ω
(
D
)
=
M, we construct the augmented Lagrange function of problem (9) as follows:
(10)
L
=
J
*
+
λ
E
2,1
+
μ
2
D
-
X
Z
-
E
F
2
+
Z
-
J
F
2
+
X
-
D
F
2
+
Y
1
,
D
-
X
Z
-
E
+
Y
2
,
Z
-
J
+
Y
3
,
X
-
D
,
where •
,
• is the inner product operator between matrices and Y
i is a Lagrange multiplier matrix, i
=
1,2
,
3. In the next part, we will propose an inexact augmented Lagrange multipliers (IALM) method to solve problem (8) or problem (9).


### 3.2. Algorithm

Inexact ALM (IALM) method employs an alternating update strategy and it minimizes or maximizes the functionL with respect to each block variable at each iteration. Let Y
=
{
Y
1
,
Y
2
,
Y
3
}.Computing
J. When J is unknown and other variables are fixed, the calculation procedure of J is as follows:
(11)
J
≔
arg
min
⁡
J
L
=
arg
min
⁡
J
J
*
+
Y
2
,
Z
-
J
+
μ
2
Z
-
J
F
2
=
arg
min
⁡
J
1
μ
J
*
+
1
2
Z
+
Y
2
μ
-
J
F
2
=
D
1
/
μ
Z
+
Y
2
μ
.Computing
Z. If matrix Z is unknown and other variables are given, Z is updated by minimizing L:
(12)
Z
≔
arg
min
⁡
Z
L
=
arg
min
⁡
Z
Y
1
,
D
-
X
Z
-
E
+
Y
2
,
Z
-
J
+
μ
2
D
-
X
Z
-
E
F
2
+
Z
-
J
F
2
=
arg
min
⁡
Z
D
-
E
+
Y
1
μ
-
X
Z
F
2
+
Z
-
J
-
Y
2
μ
F
2
.
Let g
(
Z
)
=
(
D
-
E
+
Y
1
/
μ
)
-
X
Z
F
2
+
Z
-
(
J
-
Y
2
/
μ
)
F
2. By setting the derivative of g
(
Z
) to zero, we have
(13)
∇
g
Z
=
2
X
T
X
Z
-
2
X
T
D
-
E
+
Y
1
μ
+
2
Z
-
2
J
-
Y
2
μ
=
0
or, equivalently,
(14)
Z
≔
X
T
X
+
I
-
1
X
T
D
-
E
+
Y
1
μ
+
J
-
Y
2
μ
,
where I is an n-order identity matrix.Computing
D. The update formulation of matrix D is calculated as follows:
(15)
D
≔
arg
min
⁡
D
L
=
arg
min
⁡
D
Y
1
,
D
-
X
Z
-
E
+
Y
3
,
X
-
D
+
μ
2
D
-
X
Z
-
E
F
2
+
X
-
D
F
2
=
arg
min
⁡
D
D
-
X
Z
+
E
-
Y
1
μ
F
2
+
X
+
Y
3
μ
-
D
F
2
=
1
2
X
Z
+
E
-
Y
1
μ
+
X
+
Y
3
μ
.
Considering the constraint P
Ω
(
D
)
=
M, we further obtain the iteration formulation of D
(16)
D
≔
M
+
1
2
P
Ω
-
X
Z
+
E
-
Y
1
μ
+
X
+
Y
3
μ
,
where Ω
- is the complementary set of Ω.Computing
E. FixZ
,
D
,
J
,
X, and Y and minimize L with respect to E
:
(17)
E
≔
arg
min
⁡
E
L
=
arg
min
⁡
E
λ
μ
E
2,1
+
1
2
D
-
X
Z
-
E
+
1
μ
Y
1
F
2
=
W
λ
/
μ
D
-
X
Z
+
Y
1
μ
.Computing
X. Fix Z
,
D
,
J
,
E, and Y to calculate X as follows:
(18)
X
≔
arg
min
⁡
X
L
=
arg
min
⁡
X
h
X
,
where h
(
X
)
=
D
-
X
Z
-
E
+
Y
1
/
μ
F
2
+
X
-
D
+
Y
3
/
μ
F
2. The derivative of h
(
X
) is ∇
h
(
X
)
=
2
X
Z
Z
T
-
2
(
D
-
E
+
Y
1
/
μ
)
Z
T
+
2
X
-
2
(
D
-
Y
3
/
μ
). Hence, we obtain the update of X by setting ∇
h
(
X
)
=
0:
(19)
X
≔
D
-
E
+
Y
1
μ
Z
T
+
D
-
Y
3
μ
Z
Z
T
+
I
-
1
.Computing
Y. Given Z
,
E
,
D
,
J
, and X, we calculate Y as follows
(20)
Y
≔
arg
max
⁡
Y
L
.
In the detailed implementation, Y is updated according to the following formulations:
(21)
Y
1
≔
Y
1
+
μ
D
-
X
Z
-
E
,
Y
2
≔
Y
2
+
μ
Z
-
J
,
Y
3
≔
Y
3
+
μ
X
-
D
.We denote byO
m
×
n the m
×
n zeros matrix. The whole iterative procedure is outlined in Algorithm 1. The stopping condition of Algorithm 1 can be set as
(22)
max
⁡
D
-
X
Z
-
E
F
,
Z
-
J
F
,
X
-
D
F
<
ε
,
where ε is a sufficiently small positive number.Algorithm 1:Solving ILRR by IALM.
Input: Data matrix M, sampling index set Ω, compromising parameter λ.
Initialize: D
=
M, X
=
M, Z
=
O
n
×
n, J
=
O
n
×
n, E
=
O
m
×
n, Y
1
=
O
m
×
n,
Y
2
=
O
n
×
n, Y
3
=
O
m
×
n, μ
=
1
0
-
6, μ
-
=
1
0
8, ρ
=
1.1.
Output: Z and D.
While not converged do
(1) UpdateJ according to (11).
(2) UpdateZ according to (14).
(3) UpdateD according to (16).
(4) UpdateE according to (17).
(5) UpdateX according to (19).
(6) UpdateY according to (21).
(7) Updateμ as μ:=
min
⁡
(
ρ
μ
,
μ
-
).
End while


### 3.3. Convergence

When solving ILRR via the IALM method, the block variablesJ
,
Z
,
D
,
E
,
X are updated alternatively. Now, we update simultaneously these five block variables; namely,
(23)
J
,
Z
,
D
,
E
,
X
≔
arg
min
⁡
J
,
Z
,
D
,
E
,
X
L
.
The modified method is called the exact ALM method. Since the objective function in problem (8) is continuous, the exact ALM method is convergent [18]. However, it is still difficult to prove the convergence of the IALM. There are two reasons for the difficulty: one is the existence of nonconvex constraints in (8) and the other is that the number of block variables is more than two. Nevertheless, the experimental results of Section 5 demonstrate the validity and effectiveness of Algorithm 1 in practice.


## 3.1. Model

We consider an incomplete data matrixM
∈
R
m
×
n and denote the sampling index set by Ω. The (
i
,
j
)th entry M
i
j of M is missing if and only if (
i
,
j
)
∉
Ω. For the sake of convenience, we set all missing entries of M to zeros. To recover simultaneously the missing entries and the low-rank subspace structure, we construct an incomplete low-rank representation (ILRR) model:
(7)
min
⁡
Z
,
E
,
D
Z
*
+
λ
E
2,1
s
.
t
.
vviv
D
=
D
Z
+
E
vvvvvv
P
Ω
(
D
)
=
M
,
where λ is a positive constant and D corresponds to the completion argument of M. If there is not any missing entry, that is, Ω
=
[
m
]
×
[
n
], then the above model is equivalent to LRR. In other words, LRR is a special case of ILRR.In order to solve conveniently the nonconvex nuclear norm minimization (7), we introduce two auxiliary matrix variables X
∈
R
m
×
n and J
∈
R
n
×
n. Under this circumstance, the above optimization problem is reformulated as
(8)
min
⁡
Z
,
E
,
D
,
J
,
X
J
*
+
λ
E
2,1
s
.
t
.
vvvvvv
D
=
X
Z
+
E
vvvvvvvv
Z
=
J
,
X
=
D
,
P
Ω
(
D
)
=
M
.
This minimization problem is equivalent to
(9)
min
⁡
Z
,
E
,
D
,
J
,
X
J
*
+
λ
E
2,1
vvvvvvvvvvv
+
μ
2
D
-
X
Z
-
E
F
2
+
Z
-
J
F
2
+
X
-
D
F
2
s
.
t
.
vvvviiv
D
=
X
Z
+
E
vvvvvviivv
Z
=
J
,
X
=
D
,
P
Ω
(
D
)
=
M
,
where the factor μ
>
0. Without considering the constraint P
Ω
(
D
)
=
M, we construct the augmented Lagrange function of problem (9) as follows:
(10)
L
=
J
*
+
λ
E
2,1
+
μ
2
D
-
X
Z
-
E
F
2
+
Z
-
J
F
2
+
X
-
D
F
2
+
Y
1
,
D
-
X
Z
-
E
+
Y
2
,
Z
-
J
+
Y
3
,
X
-
D
,
where •
,
• is the inner product operator between matrices and Y
i is a Lagrange multiplier matrix, i
=
1,2
,
3. In the next part, we will propose an inexact augmented Lagrange multipliers (IALM) method to solve problem (8) or problem (9).


## 3.2. Algorithm

Inexact ALM (IALM) method employs an alternating update strategy and it minimizes or maximizes the functionL with respect to each block variable at each iteration. Let Y
=
{
Y
1
,
Y
2
,
Y
3
}.Computing
J. When J is unknown and other variables are fixed, the calculation procedure of J is as follows:
(11)
J
≔
arg
min
⁡
J
L
=
arg
min
⁡
J
J
*
+
Y
2
,
Z
-
J
+
μ
2
Z
-
J
F
2
=
arg
min
⁡
J
1
μ
J
*
+
1
2
Z
+
Y
2
μ
-
J
F
2
=
D
1
/
μ
Z
+
Y
2
μ
.Computing
Z. If matrix Z is unknown and other variables are given, Z is updated by minimizing L:
(12)
Z
≔
arg
min
⁡
Z
L
=
arg
min
⁡
Z
Y
1
,
D
-
X
Z
-
E
+
Y
2
,
Z
-
J
+
μ
2
D
-
X
Z
-
E
F
2
+
Z
-
J
F
2
=
arg
min
⁡
Z
D
-
E
+
Y
1
μ
-
X
Z
F
2
+
Z
-
J
-
Y
2
μ
F
2
.
Let g
(
Z
)
=
(
D
-
E
+
Y
1
/
μ
)
-
X
Z
F
2
+
Z
-
(
J
-
Y
2
/
μ
)
F
2. By setting the derivative of g
(
Z
) to zero, we have
(13)
∇
g
Z
=
2
X
T
X
Z
-
2
X
T
D
-
E
+
Y
1
μ
+
2
Z
-
2
J
-
Y
2
μ
=
0
or, equivalently,
(14)
Z
≔
X
T
X
+
I
-
1
X
T
D
-
E
+
Y
1
μ
+
J
-
Y
2
μ
,
where I is an n-order identity matrix.Computing
D. The update formulation of matrix D is calculated as follows:
(15)
D
≔
arg
min
⁡
D
L
=
arg
min
⁡
D
Y
1
,
D
-
X
Z
-
E
+
Y
3
,
X
-
D
+
μ
2
D
-
X
Z
-
E
F
2
+
X
-
D
F
2
=
arg
min
⁡
D
D
-
X
Z
+
E
-
Y
1
μ
F
2
+
X
+
Y
3
μ
-
D
F
2
=
1
2
X
Z
+
E
-
Y
1
μ
+
X
+
Y
3
μ
.
Considering the constraint P
Ω
(
D
)
=
M, we further obtain the iteration formulation of D
(16)
D
≔
M
+
1
2
P
Ω
-
X
Z
+
E
-
Y
1
μ
+
X
+
Y
3
μ
,
where Ω
- is the complementary set of Ω.Computing
E. FixZ
,
D
,
J
,
X, and Y and minimize L with respect to E
:
(17)
E
≔
arg
min
⁡
E
L
=
arg
min
⁡
E
λ
μ
E
2,1
+
1
2
D
-
X
Z
-
E
+
1
μ
Y
1
F
2
=
W
λ
/
μ
D
-
X
Z
+
Y
1
μ
.Computing
X. Fix Z
,
D
,
J
,
E, and Y to calculate X as follows:
(18)
X
≔
arg
min
⁡
X
L
=
arg
min
⁡
X
h
X
,
where h
(
X
)
=
D
-
X
Z
-
E
+
Y
1
/
μ
F
2
+
X
-
D
+
Y
3
/
μ
F
2. The derivative of h
(
X
) is ∇
h
(
X
)
=
2
X
Z
Z
T
-
2
(
D
-
E
+
Y
1
/
μ
)
Z
T
+
2
X
-
2
(
D
-
Y
3
/
μ
). Hence, we obtain the update of X by setting ∇
h
(
X
)
=
0:
(19)
X
≔
D
-
E
+
Y
1
μ
Z
T
+
D
-
Y
3
μ
Z
Z
T
+
I
-
1
.Computing
Y. Given Z
,
E
,
D
,
J
, and X, we calculate Y as follows
(20)
Y
≔
arg
max
⁡
Y
L
.
In the detailed implementation, Y is updated according to the following formulations:
(21)
Y
1
≔
Y
1
+
μ
D
-
X
Z
-
E
,
Y
2
≔
Y
2
+
μ
Z
-
J
,
Y
3
≔
Y
3
+
μ
X
-
D
.We denote byO
m
×
n the m
×
n zeros matrix. The whole iterative procedure is outlined in Algorithm 1. The stopping condition of Algorithm 1 can be set as
(22)
max
⁡
D
-
X
Z
-
E
F
,
Z
-
J
F
,
X
-
D
F
<
ε
,
where ε is a sufficiently small positive number.Algorithm 1:Solving ILRR by IALM.
Input: Data matrix M, sampling index set Ω, compromising parameter λ.
Initialize: D
=
M, X
=
M, Z
=
O
n
×
n, J
=
O
n
×
n, E
=
O
m
×
n, Y
1
=
O
m
×
n,
Y
2
=
O
n
×
n, Y
3
=
O
m
×
n, μ
=
1
0
-
6, μ
-
=
1
0
8, ρ
=
1.1.
Output: Z and D.
While not converged do
(1) UpdateJ according to (11).
(2) UpdateZ according to (14).
(3) UpdateD according to (16).
(4) UpdateE according to (17).
(5) UpdateX according to (19).
(6) UpdateY according to (21).
(7) Updateμ as μ:=
min
⁡
(
ρ
μ
,
μ
-
).
End while


## 3.3. Convergence

When solving ILRR via the IALM method, the block variablesJ
,
Z
,
D
,
E
,
X are updated alternatively. Now, we update simultaneously these five block variables; namely,
(23)
J
,
Z
,
D
,
E
,
X
≔
arg
min
⁡
J
,
Z
,
D
,
E
,
X
L
.
The modified method is called the exact ALM method. Since the objective function in problem (8) is continuous, the exact ALM method is convergent [18]. However, it is still difficult to prove the convergence of the IALM. There are two reasons for the difficulty: one is the existence of nonconvex constraints in (8) and the other is that the number of block variables is more than two. Nevertheless, the experimental results of Section 5 demonstrate the validity and effectiveness of Algorithm 1 in practice.


## 4. Model Extensions

In ILRR model, the main aim of the termE
2,1 is to enhance the robustness to noise and outliers. If we do not consider outliers, then E
2,1 should be replaced with E
1. For the new ILRR model, we can design an algorithm by only revising Step 4 of Algorithm 1 as follows:
(24)
E
≔
arg
min
⁡
E
λ
μ
E
1
+
1
2
D
-
X
Z
-
E
+
1
μ
Y
1
F
2
=
S
λ
/
μ
D
-
X
Z
+
Y
1
μ
.
If we substitute E
F
2 for E
2,1 and set Z
=
Z
T, then problem (7) is the incomplete version of low-rank subspace clustering (LRSC) with uncorrupted data [9]. If we replace Z
* and E
2,1 by Z
1 and E
1, respectively, and incorporate diag
⁡
(
Z
)
=
0 into the constraints, then problem (7) is the incomplete version of sparse subspace clustering (SSC) without dense errors [19].ILRR uses the dataD itself as the dictionary. Now, we extend the dictionary and noise sparsity to the more general cases. As a result, we obtain a comprehensive form of ILRR:
(25)
min
⁡
Z
,
E
,
A
,
D
Z
*
+
λ
E
l
s
.
t
.
vvviv
D
=
A
Z
+
E
,
P
Ω
(
D
)
=
M
,
where A
∈
R
m
×
r represents the dictionary, Z
∈
R
r
×
n is the coefficients matrix, and E
l indicates a certain norm of E. If A is an m-order identity matrix and E
l is chosen as E
1, then problem (25) corresponds to the incomplete version of RPCA [20]. If we further reinforce λ
=
0, then problem (25) becomes the equivalent formulation of MC [16]. Moreover, if A is an unknown orthogonal matrix and λ
=
0, then problem (25) is equivalent to matrix decomposition method for MC [21]. Finally, if we let D and A be stacked by the testing samples and the training samples, respectively, let Z
* be replaced by Z
1, and let λ
=
0, then problem (25) is changed into the incomplete version of robust pattern recognition via sparse representation [22].


## 5. Experiments

In this section, we validate the effectiveness and efficiency of the proposed method by carrying out experiments on synthetic data and real-world datasets. The experimental results of incomplete low-rank representation (ILRR) are compared with that of other state-of-the-art methods: sparse subspace clustering (SSC), low-rank subspace clustering (LRSC), and low-rank representation (LRR). For the latter three methods, the missing values are replaced by zeros. For SSC and LRSC, their parameters are tuned to achieve the best performance. The tolerant errorε is set to 1
0
-
8 in all experiments.


### 5.1. Synthetic Data

We generate randomly an orthogonal matrixU
1
∈
R
200
×
4 and a rotation matrix T
∈
R
200
×
200. Four other orthogonal matrices are constructed as U
i
+
1
=
T
U
i, i
=
1,2
,
3,4. Thus, five independent low-rank subspaces {
S
i
}
i
=
1
5
⊂
R
200 are spanned by the columns of U
i, respectively. We draw 40 data vectors from each subspace by M
i
=
U
i
Q
i, i
=
1
,
…
,
5, where the entries of Q
i
∈
R
4
×
40 are independent of each other and they obey standard normal distributions. We set M
′
=
(
M
1
,
…
,
M
5
) and choose randomly its 20 column vectors to be corrupted. In this part, the chosen column vector m is contaminated by Gaussian noise with zero mean and standard deviation 0.1
m
2. The resulting matrix is expressed as M
′′.We draw samples onM
′′ according to a uniform distribution and denote by Ω the sampling index set. The sampling ratio (SR) is defined as SR
=
Ω
/
20
0
2, where Ω is the cardinality of Ω and SR
=
1 means that no entry is missing. Hence, an incomplete matrix is generated by M
=
P
Ω
(
M
′′
). The trade-off parameter λ in both LRR and ILRR is set to 0.1. After running Algorithm 1, we obtain the optimal low-rank representation matrix Z. On the basis of Z, we construct an affinity matrix Z
~
=
(
Z
+
Z
T
)
/
2, where • means the absolute value operator. Then we choose spectral clustering [23] as the clustering algorithm and evaluate the clustering performance by normalized mutual information (NMI). Let C be a set of true cluster labels and let C
′ be a set of clusters obtained from the spectral clustering algorithm. NMI is calculated as
(26)
NMI
=
MI
(
C
,
C
′
)
H
(
C
)
H
(
C
′
)
,
where MI
(
C
,
C
′
) is the mutual information metric and H
(
C
) is the entropy of C. NMI takes values in [
0,1
] and a larger NMI value indicates a better clustering performance.In the experimental implementation, we vary the SR from 0.2 to 1 with an interval of 0.1. For each fixed SR, we repeat the experiments 10 times and report the average NMI. We first compare the affinity matricesZ
~ produced by SSC, LRSC, LRR, and ILRR, as shown partially in Figure 1. From Figure 1, we observe that our method exhibits obvious block structures compared to other three methods, whereas SSC, LRSC, and LRR show no block-diagonal structure with SR
=
0.3. This observation means that only ILRR can keep compact representation for the same subspace and divergent representation for different subspaces when a large number of values are missing.Affinity matrices comparison on synthetic data.
(a)
SSC (SR = 0.5)
(b)
LRSC (SR = 0.5)
(c)
LRR (SR = 0.5)
(d)
ILRR (SR = 0.5)
(e)
SSC (SR = 0.3)
(f)
LRSC (SR = 0.3)
(g)
LRR (SR = 0.3)
(h)
ILRR (SR = 0.3)Secondly, we compare NMI values of ILRR with that of other three methods at different SR, as shown in Figure2. It can be seen from this figure that NMI values of SSC, LRR, and ILRR are almost one if SR
≥
0.7, while ILRR has higher NMI values than other three methods if SR
≤
0.6. In other words, the NMI values of SSC, LRSC, and LRR are reduced drastically with the decreasing of SR. These observations verify that ILRR is more robust than other methods in the presence of missing values.Figure 2
NMI comparison on synthetic data.


### 5.2. Face Clustering

We carry out face clustering experiments on a part of Extended Yale Face Database B [24] with large corruptions. This whole database consists of 38 objects and each object has about 64 images. We choose the first 10 objects and each image is resized into 32 × 32. Thus, the face images dataset is represented by a matrix with size of 1024 × 640. Each column of the data matrix is normalized to an l
2 unit length in consideration of variable illumination conditions and poses.The generation manner of sampling setΩ is similar to that of the previous part. We vary the values of SR from 0.1 to 1 with an interval of 0.1 and set λ
=
1.2 in LRR and ILRR. The comparison of NMI values is compared among SSC, LRSC, LRR, and ILRR, as shown in Figure 3, where each NMI value is the average result of ten repeated experiments. It can be seen from Figure 3 that ILRR achieves relatively stable NMI values if SR
≥
0.2, while other three methods obtain much worse NMI values than ILRR if SR
≤
0.9. This observation shows that SSC, LRSC, and LRR are more sensitive than ILRR on SR.Figure 3
NMI comparison on Extended Yale B.Furthermore, ILRR has an advantage in recovering the low-rank components over other three methods. In the following, we give the recovery performance contrast of ILRR. Here, we only consider two different SR; that is,SR
=
0.3 and SR
=
0.6. For these two given SR, the original images, sampled images, recovered images, and noise images are shown partially in Figures 4 and 5, respectively. Among these sampled images, the unsampled entries are shown in white. From these two figures, we can see that ILRR not only corrects automatically the corruptions (shadow and noise) but also recovers efficiently the low-rank components.Face images recovery of ILRR on Extended Yale B withSR
=
0.3.
(a)
Original images
(b)
Sampled images
(c)
Recovered images
(d)
Noise imagesFace images recovery of ILRR on Extended Yale B withSR
=
0.6.
(a)
Original images
(b)
Sampled images
(c)
Recovered images
(d)
Noise images


### 5.3. Motion Segmentation

In this part, we test the proposed ILRR method for the task of motion segmentation. We consider eight sequences of outdoor traffic scenes, a subset of the Hopkins 155 dataset [25]. These sequences were taken by a moving handheld camera and they tracked two cars translating and rotating on a street, as shown partly in Figure 6. These sequences are drawn from two or three motions, where one motion corresponds to one subspace. There are 8 clustering tasks in total since motion segmentation of each sequence is a sole clustering task. The tasks of motion segmentation are carried out according to the given features extracted and tracked in multiple frames of the above video sequences.Figure 6
Images from traffic sequences on the Hopkins 155 dataset.The extracted feature points of each sequence can be reshaped into an approximately low-rank matrix withn columns, where n equals the number of feature points. In the detailed experimental implementation, we consider different SR varying from 0.2 to 1 with an interval 0.2. The regularization parameter set λ in LRR and ILRR is set to 2. For fixed sequence and fixed SR, each method is repeated 10 times and the mean NMI values are recorded. We report the mean and the standard derivation of NMI values among 8 sequences, as shown in Table 1.Table 1
NMI (%) comparison of different methods on traffic sequences.
SR
SSC
LRSC
LRR
ILRR
0.2
5.15 ± 4.97
8.76 ± 4.66
9.97 ± 5.26
66.18 ± 15.40
0.4
13.74 ± 7.00
15.61 ± 10.50
15.07 ± 11.45
89.98 ± 13.24
0.6
21.45 ± 15.88
18.48 ± 11.84
17.78 ± 13.71
90.60 ± 13.72
0.8
50.97 ± 25.52
18.85 ± 14.06
17.46 ± 15.71
96.71 ± 6.84
1.0
100 ± 0.00
96.38 ± 7.60
96.83 ± 6.41
96.83 ± 6.41From Table1, we can see that ILRR obtains very high NMI values especially for SR
≥
0.2, while NMI values of other three methods are unacceptable for SR
≤
0.8. Although SSC segments exactly each subspace when SR
=
1.0, small SR has a fatal influence on SSC’s segmentation performance. In summary, ILRR is more robust to a large number of missing values than other three methods.


## 5.1. Synthetic Data

We generate randomly an orthogonal matrixU
1
∈
R
200
×
4 and a rotation matrix T
∈
R
200
×
200. Four other orthogonal matrices are constructed as U
i
+
1
=
T
U
i, i
=
1,2
,
3,4. Thus, five independent low-rank subspaces {
S
i
}
i
=
1
5
⊂
R
200 are spanned by the columns of U
i, respectively. We draw 40 data vectors from each subspace by M
i
=
U
i
Q
i, i
=
1
,
…
,
5, where the entries of Q
i
∈
R
4
×
40 are independent of each other and they obey standard normal distributions. We set M
′
=
(
M
1
,
…
,
M
5
) and choose randomly its 20 column vectors to be corrupted. In this part, the chosen column vector m is contaminated by Gaussian noise with zero mean and standard deviation 0.1
m
2. The resulting matrix is expressed as M
′′.We draw samples onM
′′ according to a uniform distribution and denote by Ω the sampling index set. The sampling ratio (SR) is defined as SR
=
Ω
/
20
0
2, where Ω is the cardinality of Ω and SR
=
1 means that no entry is missing. Hence, an incomplete matrix is generated by M
=
P
Ω
(
M
′′
). The trade-off parameter λ in both LRR and ILRR is set to 0.1. After running Algorithm 1, we obtain the optimal low-rank representation matrix Z. On the basis of Z, we construct an affinity matrix Z
~
=
(
Z
+
Z
T
)
/
2, where • means the absolute value operator. Then we choose spectral clustering [23] as the clustering algorithm and evaluate the clustering performance by normalized mutual information (NMI). Let C be a set of true cluster labels and let C
′ be a set of clusters obtained from the spectral clustering algorithm. NMI is calculated as
(26)
NMI
=
MI
(
C
,
C
′
)
H
(
C
)
H
(
C
′
)
,
where MI
(
C
,
C
′
) is the mutual information metric and H
(
C
) is the entropy of C. NMI takes values in [
0,1
] and a larger NMI value indicates a better clustering performance.In the experimental implementation, we vary the SR from 0.2 to 1 with an interval of 0.1. For each fixed SR, we repeat the experiments 10 times and report the average NMI. We first compare the affinity matricesZ
~ produced by SSC, LRSC, LRR, and ILRR, as shown partially in Figure 1. From Figure 1, we observe that our method exhibits obvious block structures compared to other three methods, whereas SSC, LRSC, and LRR show no block-diagonal structure with SR
=
0.3. This observation means that only ILRR can keep compact representation for the same subspace and divergent representation for different subspaces when a large number of values are missing.Affinity matrices comparison on synthetic data.
(a)
SSC (SR = 0.5)
(b)
LRSC (SR = 0.5)
(c)
LRR (SR = 0.5)
(d)
ILRR (SR = 0.5)
(e)
SSC (SR = 0.3)
(f)
LRSC (SR = 0.3)
(g)
LRR (SR = 0.3)
(h)
ILRR (SR = 0.3)Secondly, we compare NMI values of ILRR with that of other three methods at different SR, as shown in Figure2. It can be seen from this figure that NMI values of SSC, LRR, and ILRR are almost one if SR
≥
0.7, while ILRR has higher NMI values than other three methods if SR
≤
0.6. In other words, the NMI values of SSC, LRSC, and LRR are reduced drastically with the decreasing of SR. These observations verify that ILRR is more robust than other methods in the presence of missing values.Figure 2
NMI comparison on synthetic data.


## 5.2. Face Clustering

We carry out face clustering experiments on a part of Extended Yale Face Database B [24] with large corruptions. This whole database consists of 38 objects and each object has about 64 images. We choose the first 10 objects and each image is resized into 32 × 32. Thus, the face images dataset is represented by a matrix with size of 1024 × 640. Each column of the data matrix is normalized to an l
2 unit length in consideration of variable illumination conditions and poses.The generation manner of sampling setΩ is similar to that of the previous part. We vary the values of SR from 0.1 to 1 with an interval of 0.1 and set λ
=
1.2 in LRR and ILRR. The comparison of NMI values is compared among SSC, LRSC, LRR, and ILRR, as shown in Figure 3, where each NMI value is the average result of ten repeated experiments. It can be seen from Figure 3 that ILRR achieves relatively stable NMI values if SR
≥
0.2, while other three methods obtain much worse NMI values than ILRR if SR
≤
0.9. This observation shows that SSC, LRSC, and LRR are more sensitive than ILRR on SR.Figure 3
NMI comparison on Extended Yale B.Furthermore, ILRR has an advantage in recovering the low-rank components over other three methods. In the following, we give the recovery performance contrast of ILRR. Here, we only consider two different SR; that is,SR
=
0.3 and SR
=
0.6. For these two given SR, the original images, sampled images, recovered images, and noise images are shown partially in Figures 4 and 5, respectively. Among these sampled images, the unsampled entries are shown in white. From these two figures, we can see that ILRR not only corrects automatically the corruptions (shadow and noise) but also recovers efficiently the low-rank components.Face images recovery of ILRR on Extended Yale B withSR
=
0.3.
(a)
Original images
(b)
Sampled images
(c)
Recovered images
(d)
Noise imagesFace images recovery of ILRR on Extended Yale B withSR
=
0.6.
(a)
Original images
(b)
Sampled images
(c)
Recovered images
(d)
Noise images


## 5.3. Motion Segmentation

In this part, we test the proposed ILRR method for the task of motion segmentation. We consider eight sequences of outdoor traffic scenes, a subset of the Hopkins 155 dataset [25]. These sequences were taken by a moving handheld camera and they tracked two cars translating and rotating on a street, as shown partly in Figure 6. These sequences are drawn from two or three motions, where one motion corresponds to one subspace. There are 8 clustering tasks in total since motion segmentation of each sequence is a sole clustering task. The tasks of motion segmentation are carried out according to the given features extracted and tracked in multiple frames of the above video sequences.Figure 6
Images from traffic sequences on the Hopkins 155 dataset.The extracted feature points of each sequence can be reshaped into an approximately low-rank matrix withn columns, where n equals the number of feature points. In the detailed experimental implementation, we consider different SR varying from 0.2 to 1 with an interval 0.2. The regularization parameter set λ in LRR and ILRR is set to 2. For fixed sequence and fixed SR, each method is repeated 10 times and the mean NMI values are recorded. We report the mean and the standard derivation of NMI values among 8 sequences, as shown in Table 1.Table 1
NMI (%) comparison of different methods on traffic sequences.
SR
SSC
LRSC
LRR
ILRR
0.2
5.15 ± 4.97
8.76 ± 4.66
9.97 ± 5.26
66.18 ± 15.40
0.4
13.74 ± 7.00
15.61 ± 10.50
15.07 ± 11.45
89.98 ± 13.24
0.6
21.45 ± 15.88
18.48 ± 11.84
17.78 ± 13.71
90.60 ± 13.72
0.8
50.97 ± 25.52
18.85 ± 14.06
17.46 ± 15.71
96.71 ± 6.84
1.0
100 ± 0.00
96.38 ± 7.60
96.83 ± 6.41
96.83 ± 6.41From Table1, we can see that ILRR obtains very high NMI values especially for SR
≥
0.2, while NMI values of other three methods are unacceptable for SR
≤
0.8. Although SSC segments exactly each subspace when SR
=
1.0, small SR has a fatal influence on SSC’s segmentation performance. In summary, ILRR is more robust to a large number of missing values than other three methods.


## 6. Conclusions

In this paper, we investigate the model of low-rank representation for incomplete data, which can be regarded as the generalization of low-rank representation and matrix completion. For the model of incomplete low-rank representation, we propose an iterative scheme based on augmented Lagrange multipliers method. Experimental results show that the proposed method is feasible and efficient in recovering low-rank structure, completing missing entries, and removing noise. It still needs further research on how to construct a general model of low-rank matrix recovery and design the corresponding algorithm.



---

*Source: 439417-2014-12-31.xml*