低秩表示法：解决多子空间数据聚类与异常检测问题
需积分: 33 199 浏览量
更新于2024-07-21
1
收藏 963KB PDF 举报
本文主要探讨了数据流形在图像处理中的应用，特别是关注数据分割和运动分割技术。研究聚焦于一种名为“低秩表示”(Low-Rank Representation, LRR)的方法，它在解决子空间聚类问题时展现出显著的优势。在给定的数据集，假设这些样本（向量）大致来自多个子空间的组合，目标是将它们有效地分类到各自的子空间，并同时剔除可能存在的异常值或噪声点。
LRR方法的核心思想是提出一个创新的优化目标函数，该函数旨在寻找所有候选表示中最为低秩的一个。这种低秩约束有助于捕捉数据内在的结构，即样本在高维空间中的子空间分布特征。通过最小化数据矩阵的秩，LRR能够发现数据点之间的协同模式，从而形成紧凑且具有代表性的子空间表示。
具体来说，LRR算法包括以下几个步骤：
1. **数据预处理**：首先，对输入的图像数据进行预处理，可能涉及归一化、降噪等步骤，以确保数据的质量和一致性。
2. **构建低秩模型**：对于每个数据点，构建一个包含其邻域内其他点的低秩矩阵，使得数据点可以通过这些邻域内的其他点近似表示，而不是直接依赖单个点。
3. **求解优化问题**：利用数学优化工具（如梯度下降或核方法），找到使整个数据集低秩表示的最优参数，这通常涉及到求解一个凸优化问题。
4. **子空间聚类**：根据每个数据点在低秩表示中的位置，将其分配到最接近的子空间中。低秩性使得数据点更容易被划分到它们所属的子空间中，而远离低秩模型的点则被视为异常。
5. **异常检测**：通过比较数据点与低秩模型的距离，可以识别并剔除潜在的异常值，这些点的表示通常与实际子空间不一致。
LRR因其在处理图像中的优异性能，尤其是在复杂背景下区分不同运动模式、分离背景和前景以及在图像分割任务中的应用，而在计算机视觉和机器学习领域受到广泛关注。此外，由于其理论基础深厚且在实际问题中效果显著，LRR还启发了后续的研究者开发更多的低秩表示相关算法和扩展，如用于异常检测、视频监控、图像分类等领域。
4
B. Relations Between Segmentation and Row Space
Let X
0
with skinny SVD U
0
Σ
0
V
T
0
be a collection of data
samples strictly drawn from a union of multiple subspaces
(i.e., X
0
is clean), the subspace membership of the samples
is determined by the row space of X
0
. Indeed, as shown
in [12], when subspaces are independent, V
0
V
T
0
forms a
block-diagonal matrix: the (i, j)-th entry of V
0
V
T
0
can be
nonzero only if the i-th and j-th samples are from the same
subspace. Hence, this matrix, termed as Shape Interaction
Matrix (SIM) [12], has been widely used for subspace seg-
mentation. Previous approaches simply compute the SVD of
the data matrix X = U
X
Σ
X
V
T
X
and then use |V
X
V
T
X
|
1
for
subspace segmentation. However, in the presence of outliers
and corruptions, V
X
can be far away from V
0
and thus the
segmentation using such approaches is inaccurate. In contrast,
we show that LRR can recover V
0
V
T
0
even when the data
matrix X is contaminated by outliers.
If the subspaces are not independent, V
0
V
T
0
may not be
strictly block-diagonal. This is indeed well expected, since
when the subspaces have nonzero (nonempty) intersections,
then some samples may belong to multiple subspaces simul-
taneously. When the subspaces are pairwise disjoint (but not
independent), our extensive numerical experiments show that
V
0
V
T
0
may still be close to be block-diagonal, as exemplified
in Fig. 3. Hence, to recover V
0
V
T
0
is still of interest to
subspace segmentation.
C. Problem Statement
Problem 1.1 only roughly describes what we want to study.
More precisely, this paper addresses the following problem.
Problem 3.1 (Subspace Clustering): Let X
0
∈ R
d×n
with
skinny SVD U
0
Σ
0
V
0
store a set of n d-dimensional samples
(vectors) strictly drawn from a union of k subspaces {S
i
}
k
i=1
of unknown dimensions (k is unknown either). Given a set of
observation vectors X generated by
X = X
0
+ E
0
,
the goal is to recover the row space of X
0
, or to recover the
true SIM V
0
V
T
0
as equal.
The recovery of row space can guarantee high segmentation
accuracy, as analyzed in Section III-B. Also, the recovery of
row space naturally implies the success in error correction. So
it is sufficient to set the goal of subspace clustering as the
recovery of the row space identified by V
0
V
T
0
. For ease of
exploration, we consider the problem under three assumptions
of increasing practicality and difficulty.
Assumption 1: The data is clean, i.e., E
0
= 0.
Assumption 2: A fraction of the data samples are grossly
corrupted and the others are clean, i.e., E
0
has sparse column
supports as shown in Fig.2(c).
Assumption 3: A fraction of the data samples are grossly
corrupted and the others are contaminated by small Gaussian
noise, i.e., E
0
is characterized by a combination of the models
shown in Fig.2(a) and Fig.2(c).
1
For a matrix M, |M | denotes the matrix with the (i, j)-th entry being the
absolute value of [M]
ij
.
Unlike [14], the independent assumption on the subspaces is
not highlighted in this paper, because the analysis in this work
focuses on recovering V
0
V
T
0
other than a pursuit of block-
diagonal matrix.
IV. LOW-RANK REPRESENTATION FOR MATRIX
RECOVERY
In this section we abstractly present the LRR method
for recovering a matrix from corrupted observations. The
basic theorems and optimization algorithms will be presented.
The specific methods and theories for handling the subspace
clustering problem are deferred until Section V.
A. Low-Rank Representation
In order to recover the low-rank matrix X
0
from the given
observation matrix X corrupted by errors E
0
(X = X
0
+ E
0
),
it is straightforward to consider the following regularized rank
minimization problem:
min
D,E
rank (D) + λ kEk
ℓ
, s.t. X = D + E, (2)
where λ > 0 is a parameter and k·k
ℓ
indicates certain
regularization strategy, such as the squared Frobenius norm
(i.e., k · k
2
F
) used for modeling the noise as show in Fig.2(a)
[6], the ℓ
0
norm adopted by [7] for characterizing the random
corruptions as shown in Fig.2(b), and the ℓ
2,0
norm adopted
by [14], [16] for dealing with sample-specific corruptions
and outliers. Suppose D
∗
is a minimizer with respect to the
variable D, then it gives a low-rank recovery to the original
data X
0
.
The above formulation is adopted by the recently established
Robust PCA (RPCA) method [7] which has been used to
achieve the state-of-the-art performance in several applications
(e.g., [35]). However, this formulation implicitly assumes that
the underlying data structure is a single low-rank subspace.
When the data is drawn from a union of multiple subspaces,
denoted as S
1
, S
2
, ··· , S
k
, it actually treats the data as being
sampled from a single subspace defined by S =
P
k
i=1
S
i
.
Since the sum
P
k
i=1
S
i
can be much larger than the union
∪
k
i=1
S
i
, the specifics of the individual subspaces are not well
considered and so the recovery may be inaccurate.
To better handle the mixed data, here we suggest a more
general rank minimization problem defined as follows:
min
Z,E
rank (Z) + λ kEk
ℓ
, s.t. X = AZ + E, (3)
where A is a “dictionary” that linearly spans the data space.
We call the minimizer Z
∗
(with regard to the variable Z)
the “lowest-rank representation” of data X with respect to a
dictionary A. After obtaining an optimal solution (Z
∗
, E
∗
),
we could recover the original data by using AZ
∗
(or X −
E
∗
). Since rank (AZ
∗
) ≤ rank (Z
∗
), AZ
∗
is also a low-
rank recovery to the original data X
0
. By setting A = I, the
formulation (3) falls back to (2). So LRR could be regarded
as a generalization of RPCA that essentially uses the standard
bases as the dictionary. By choosing an appropriate dictionary
A, as we will see, the lowest-rank representation can recover
the underlying row space so as to reveal the true segmentation
of data. So, LRR could handle well the data drawn from a
union of multiple subspaces.
剩余15页未读，继续阅读
2018-11-13 上传
2015-09-28 上传
2021-04-03 上传
2024-05-22 上传
2022-09-23 上传
2021-02-07 上传
2024-07-11 上传
点击了解资源详情
qq_22767445
- 粉丝: 0
- 资源: 1
我的内容管理
展开
最新资源
- 新型智能电加热器：触摸感应与自动温控技术
- 社区物流信息管理系统的毕业设计实现
- VB门诊管理系统设计与实现(附论文与源代码)
- 剪叉式高空作业平台稳定性研究与创新设计
- DAMA CDGA考试必备：真题模拟及章节重点解析
- TaskExplorer：全新升级的系统监控与任务管理工具
- 新型碎纸机进纸间隙调整技术解析
- 有腿移动机器人动作教学与技术存储介质的研究
- 基于遗传算法优化的RBF神经网络分析工具
- Visual Basic入门教程完整版PDF下载
- 海洋岸滩保洁与垃圾清运服务招标文件公示
- 触摸屏测量仪器与粘度测定方法
- PSO多目标优化问题求解代码详解
- 有机硅组合物及差异剥离纸或膜技术分析
- Win10快速关机技巧：去除关机阻止功能
- 创新打印机设计：速释打印头与压纸辊安装拆卸便捷性
