英语原文共 16 页，剩余内容已隐藏，支付完成后下载完整资料
计算机视觉中的稳健拟合：简单还是难？
摘 要
稳健的模型拟合在计算机视觉中起着至关重要的作用，对稳健拟合算法的研究仍然很活跃。可以说，最受欢迎的计算机视觉拟合范式是共识最大化，力求找到最大化内部数量的模型参数。尽管在用于共识最大化的算法中有显着的发展，但是在计算机视觉文献中缺乏对该问题的基本分析。特别是，共识最大化是否“易处理”仍然是一个尚未严格处理的问题，因此难以评估和比较所提出的算法的性能，相对于理论上可实现的性能。为了阐明这些问题，我们提出了几种计算硬度结果，用于共识最大化。我们的结果强调了问题的基本难以解决的问题，并解决了文献中存在的一些含糊之处。
关键词：鲁棒拟合，一致最大化，内部集最大化，计算硬度。
1 NP-硬度
MAXCON的决定版本如下。
问题2（MAXCON-D）。给定的数据D = {(ai, bi)}N ,一个内点阈ǫ isin;R ，和一个数psi;isin;N ，确实存在x isin; Rd，使得Psi;ǫ(x | D) ge; psi;？
另一个众所周知的稳健拟合范式是最小中值平方（LMS），其中我们寻找最小化残差中值的向量x
. (2)
LMS可以通过最小化第k个最大残差来推广
. （3）
其中函数kos返回其第k个最大输入值。
几何上，LMS寻找包含R d 1中一半数据点D 的最小宽度的平板R d 1中的平板由法向量x和宽度w定义为
（4）
问题（3）因此寻找包含点的k的最薄的板。（3）的决定版本如下。
问题3（k-SLAB）。给定的数据，其中的整数k其中1le; k le; N，和若干omega;#39; isin; R ，确实存在X isin; R d，使得k d的构件被包含在一个板坯ħomega;（X）的宽度在最 w #39;？[17]已经证明k-SLAB是NP完全的。
定理1.MAXCON-D是NP完全的。
证明：设D，k和w #39;定义k-SLAB的实例。通过简单地重复使用相同的D，设置和 psi; = k，可以将其简化为MAXCON-D的实例。如果答案为k-SLAB为正，则有一个X使得k从垂直距离内d谎言点通过定义从超平面X，因此Psi; ǫ（X | d）必须至少为psi;和答案MAXCON-D也是正数。相反，如果MAXCON-D的答案为正，那么有一个x使得psi;点的垂直距离小于ǫ到x，因此以宽度x最多w #39; 为中心的平板可以包围k个点，并且k-SLAB的答案也是正的。
MAXCON-D的NP完全性意味着优化版本MAXCON的NP-硬度。见第二节1.1关于NP-硬度的含义。
2 参数化复杂性
参数化复杂性是算法的一个分支，它研究输入中结构参数问题的固有难度[16]。在本节中，我们将报告MAXCON的几个参数化复杂度结果。
首先，共识设置 Cǫ(x | D) 的X被定义为
Cǫ(x | D) := {i isin; {1, . . . , N } | |aT x minus; bi| le; ǫ} (5)
因此，共识（1）的等价定义
Psi;ǫ(x | D) = |Cǫ(x | D)|. (6)
此后，我们不区分索引D 子集的整数子集Csube;{1 ，...，N }和由C索引的实际数据。
3.1 维度中的XP
以下是在C索引的输入数据上定义的切比雪夫逼近问题[29，第2章]：
（7）
问题（7）具有线性规划（LP）公式
（LP [C]）
这可以在多项式时间内求解。切比雪夫近似也具有以下特性。
引理1 有一个子集B的 C，其中 |B|le;d 1 ，使得
（8）
证明。见[29，第2.3节]。
我们将B称为C的基础。数学上，B是LP [C]的有效约束集，因此可以容易地计算基数。实际上，LP [B]和LP [C]具有相同的最小化器。此外，对于任何大小为d 1的子集B，de la Vall#39;ee-Poussin的方法可以在时间多项式下解析LP [B]到d ; 有关详细信息，请参见[29，第2章]。
让X是任意的候选解决方案MAXCON，和（X .gamma;）是minimisers到LP [C ǫ（X | d）]，即，在一致集合的切比雪夫逼近问题X。可以建立以下属性。
引理2 Psi;ǫ(xcirc; | D) ge; Psi;ǫ(x | D)。
证明：通过构造，gamma;le; ǫ。因此，如果（a i，b i）是x的内部，即| a T ix - b i|le;ǫ，然后|aT i x - b i| le;gamma;le;ǫ，即（ai，b i）也是内点到X。因此，x的一致性 不小于x的一致性。
Lemmas 1和2提出了一种用于共识最大化的基本算法，该算法试图找到最大共识集的基础，如下面定理的证明所包含的那样。
定理2. MAXCON是维d中的XP（切片多项式）。
证明：设X *是MAXCON-d与肯定的答案，即Psi;实例见证Psi;ǫ(x | D) ge; psi;。设（X）是minimisers到LP[Cǫ(x | D)]。由引理2，xcirc;也是一个积极的见证实例。通过引理1，xcirc;可以 通过列举所有找到d上的每个，解决切比雪夫逼近（7）。总共需要检查子集; 包括评估Psi;ǫ的时间Psi;ǫ（x | D）对于每个候选者，这个简单算法的运行时间是O(N d 2poly(d))，对于固定的d，它是N的多项式。
定理2表明，对于固定维数d，MAXCON可以在时间多项式中求解测量数N（这与[8,12]中的结果一致）。然而，这并不意味着MAXCON易于处理（遵循复杂性理论中易处理性的标准含义[15,16]）。此外，在实际应用中，d可以是大的（例如，d ge;5），从而上面的基本的算法将不高效的为大N。
3.2 W[1]-hard in the dimension
我们可以从全局最优算法的运行时指数中删除d吗？通过在维度中建立W [1] - 硬度，本节显示它是不可能的。我们的证明受到[30，第5节]的启发，但非常显着。首先，源问题如下。
问题4（k-CLIQUE）。鉴于无向图G =（V，E）具有顶点集V和边缘集E和参数k isin;N ，确实存在一个集团中G 与K顶点？
k-CLIQUE是W [1] -hard wrt参数k [31]。在这里，我们演示FPT从k-CLIQUE减少到具有固定尺寸d的 MAXCON-D 。
生成输入数据给定输入图G =（V，E），其中V ={1 ，...，M }和大小k，我们构造一个（k 1）维点集DG ={(ai, bi)}N = DV cup; DE 如下：
集合D V定义为
其中
av alpha;=[0，...，0,1,0,... 0] Ť （10）
是一个0的k维向量，除了在第alpha;个元素，其值为1，和
(11)
集合D E定义为
DE = {(au,v , bu,v ) | u, v = 1, . . . , M,
hu, vi isin; E, hv, ui isin; E, (12)
alpha;, beta; = 1, . . . , k,
alpha; lt; beta; },
其中
是0的k维向量，除了在值为1的第alpha;个元素和值为M的第beta;个元素之外，
（14）
大小Ndg的因此。
设置内点阈值在我们的减少，Xisin;R d是负责“选择”的顶点的子集V和边缘Euml;的ģ。首先，我们说X选择顶点v如果一个点（av alpha;，B v alpha;）isin;D V，对于一些alpha;，是一种内点到X，即，如果
， （15）
其中X alpha;是alpha;的个元素X。关键的问题是如何设置内点阈值的值ǫ，使得X选择不超过ķ顶点，或等价地，使得Psi;ǫ(x | DV ) le; k 所有X。
引理3 如果，则 Psi;ǫ(x | DV ) le; k ，平等当且仅当达到X 选择G.的k个顶点ǫ lt;1/2
证明：对于任何u和v，范围[u minus; ǫ, u ǫ] 和[v minus; ǫ, v ǫ] 不能重叠，如果
ǫ lt;1/2。因此，X alpha;至多在于范围中的一个，即，每一个元素X选择顶点中的至多一个; 参见图1，这意味着， Psi;ǫ(x | DV ) le; k 。
其次，点 (au,v , bu,v )从DE是内点到X 如果
|(au,v )T x minus; bu,v | le; ǫ equiv; |(xalpha; minus; u) M (xbeta; minus; v)| le; ǫ. (16)
如（16）所示，x的元素对负责选择G的边缘。防止每个元件对<em
全文共12032字，剩余内容已隐藏，支付完成后下载完整资料</em
资料编号：[452434]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
