基于低秩二阶密度投影的高维非参数变点检测

# 通过低秩二阶密度投影的高维非参数变点检测
来源: https://arxiv.org/html/2608.13922
郭庆  
机构: 运筹学项目  
机构: 北卡罗来纳州立大学  
机构: 北卡罗来纳州罗利市，美国  
邮箱: [Gzhang25@ncsu\.edu](mailto:)
陈兆鑫  
机构: H. Milton Stewart 工业与系统工程学院  
机构: 佐治亚理工学院  
机构: 佐治亚州亚特兰大市，美国  
邮箱: [zxchen08@gatech\.edu](mailto:)

###### 摘要
当变化前后的密度均未被参数化指定时，在高维中检测分布变化是困难的。我们提出一种基于表示的方法，该方法保留了所有至多二阶密度信息，同时用矩阵均值估计替代了密度估计。对于定义在\[-1,1\]^{d}\[\-1,1\]^\{d\}中的观测值，我们构建了一个对称特征矩阵\(H_{2}(X)\in\mathbb{R}^{(d+1)\times(d+1)}H_\{2\}(X)\\in\\mathbb\{R\}^\{\(d+1\)\\times\(d+1\)\}\)，使得\(M(f)=\mathbb{E}_{f}H_{2}(X)M(f)=\\mathbb\{E\}\_fH_\{2\}(X)\)成为密度二阶正交投影的等距编码。我们在秩-\(r\)截断后扫描矩阵CUSUM，利用投影跳跃的低秩性而非单个坐标的稀疏性。所得LR-D2估计量具有帐篷形的总体目标函数，其非渐近算子范数分析中的主导随机项按\(\sqrt{rd\log(nd)}\)缩放。对于多个变化点，我们给出了一个种子化的“逐阈值最窄”过程，并通过归纳法证明了精确恢复，该归纳法为每个未检测到的变化点保留一个隔离区间。交叉拟合的标量细化在一个折叠上学习变化的低秩方向，在另一个折叠上进行定位，达到了\(\widetilde{O}_{\mathbb{P}}(\kappa^{-2})\)误差；匹配的Le Cam下界表明该方法在对数因子意义下是最优的。通过依赖矩阵Bernstein不等式，我们得到了一个几何\(\beta\)混合的扩展。环境维度高达200、包含三个变化点的\(d=100\)序列以及一个128特征的UCI人类活动基准实验表明，该方法在计算上仍然实用，并能准确检测均值CUSUM无法察觉的纯依赖性变化。

## 1 引言
变点是指生成序列的法则发生变化的时间点。在现代应用中，每个时间点的观测值可能是一个高维向量，并且变化不必是均值偏移：依赖性、边际形状或交互作用可能发生变化，而每个坐标的均值保持不变。经典的多元方法则面临两个同时存在的障碍。首先，直接非参数密度估计受制于维数灾难。其次，一个无限制的二阶变化包含\(\Theta(d^2)\\Theta(d^\{2\})\)个坐标，因此即使科学上有意义的变化是低维的，Frobenius扫描也会累积压倒性的噪声。我们通过密度的固定表示来解决这些障碍。相对于\[\-1,1\]^\{d\}\[-1,1\]^{d}上的均匀测度，二阶投影包含坐标均值、边际二次分量和成对交互作用。通过适当的归一化，所有这些系数构成一个对称的\((d+1)\times(d+1)\)(d+1)\\times(d+1)矩阵\(M(f)M(f)\)。至关重要的是，存在一个单观测特征映射\(H_{2}H_\{2\}\)，满足\(M(f)=\mathbb{E}_{f}H_{2}(X)\)，\(\left\lVert M(f)-M(g)\right\rVert_{\mathrm{F}}=\left\lVert P_{2}(f-g)\right\rVert_{L^{2}}\)。M(f)=\\mathbb\{E\}\_fH_\{2\}(X),\\qquad\\left\\lVert M(f)\\-M(g)\\right\\rVert\_\{\\mathrm\{F\}\}=\\left\\lVert P\_\{2\}(f\\-g)\\right\\rVert\_\{L^\{2\}\}.因此，二阶投影可见的非参数变化就变成了一个矩阵均值变化，而无需估计任一密度。当投影跳跃矩阵是低秩时，秩截断在保留其总体信号的同时，对矩阵CUSUM进行了去噪。这一观点有别于坐标稀疏性。由少数潜在交互作用方向生成的稠密相关模式可能具有许多非零元素，但秩很小。它还提供了一个具体的表示学习解释：\(H_{2}H_\{2\}\)是一个确定性的二阶特征映射，数据通过局部特征分解选择变化的子空间。矩阵维度仅随\(d\)线性增长，并且保留的秩控制了有效的随机复杂性。

#### 贡献。
我们的主要贡献有四个方面。
1. 1\.我们推导了二阶密度投影的精确等距矩阵编码，并证明了在任何包含一个变化点的区间上，每个总体矩阵CUSUM都是同一跳跃矩阵的正标量倍数。所得的平方总体得分具有精确的线性定位余量。
2. 2\.我们证明了一个确定性的低秩扰动不等式，并将其与矩阵Bernstein集中不等式相结合。在有界密度条件下，主导的归一化CUSUM噪声在算子范数下为\(O_{\mathbb{P}}(\sqrt{d\log(nd)})\)O\_\{\\mathbb\{P\}\}(\\sqrt\\{d\\log(nd)\\})，给出了信号要求\(\Delta\kappa^{2}\gtrsim rd\log(nd)\)\\Delta\\kappa^\\{2\\}\\gtrsim rd\\log(nd)\)，忽略常数和低阶项。
3. 3\.我们提出了Seeded-LR-D2，一个多尺度区间删除算法。其多变点定理通过归纳法证明：无变化区间是不活跃的，每个剩余变化点都有一个活跃的平衡隔离区间，且最短的活跃区间恰好包含一个变化点。然后我们引入了Refine-LR-D2，这是一个交叉拟合的方向与定位步骤，具有接近minimax的\(\kappa^{-2}\)\\kappa^\\{-2\\}误差。
4. 4\.我们提供了可复现的合成和半合成实验。该估计量在\(d\in\{20,50,100,200\}\)d\\in\\{20,50,100,200\\}上运行，检测了一个\(d=100\)d=100序列中的三个变化点，并处理了一个128特征的UCI人类活动任务。这些设置直接验证了所声称的高维操作机制。

#### 相关工作。
高维均值变化方法利用稀疏投影或稀疏化分割（[15](https://arxiv.org/html/2608.13922#bib.bib15)；[5](https://arxiv.org/html/2608.13922#bib.bib5)；[6](https://arxiv.org/html/2608.13922#bib.bib6)）。非参数多元和函数变点方法包括核、图和局部邻域构造（[9](https://arxiv.org/html/2608.13922#bib.bib9)；[8](https://arxiv.org/html/2608.13922#bib.bib8)；[13](https://arxiv.org/html/2608.13922#bib.bib12)；[12](https://arxiv.org/html/2608.13922#bib.bib13)；[2](https://arxiv.org/html/2608.13922#bib.bib1)）。我们的方法是互补的：它在密度层面是非参数的，但针对的是通过指定的多项式投影可识别的变化，以低矩阵秩作为结构性正则化。对于多个变化点，我们借鉴了wild、逐阈值最窄和种子二分的想法（[7](https://arxiv.org/html/2608.13922#bib.bib7)；[4](https://arxiv.org/html/2608.13922#bib.bib4)；[10](https://arxiv.org/html/2608.13922#bib.bib10)）。两阶段定位架构和基于归纳的一致性论证也与最近的函数回归变点分析（[11](https://arxiv.org/html/2608.13922#bib.bib11)）相关。矩阵集中不等式基于[14](https://arxiv.org/html/2608.13922#bib.bib14)；依赖性扩展使用了[3](https://arxiv.org/html/2608.13922#bib.bib3)。

## 2 二阶密度表示
### 2.1 一个等距特征矩阵
令\(\mu=\operatorname{Unif}([\-1,1]^{d})\)\mu=\\operatorname\\{Unif\\}\\(\[\-1,1\]^\\{d\\}\)，令\(f=dP/d\mu\)f=dP/d\\mu。定义前三个勒让德多项式\(p_{0}(x)=1\)，\(p_{1}(x)=x\)，\(p_{2}(x)=\\frac{3x^{2}-1}{2}\)，其\(L^{2}(\mu)L^{2}(\\mu)\)范数的平方分别为1, 1/3, 和1/5。至多二阶投影为\(P_{2}f(x)=1+\sum_{j=1}^{d}a_{j}x_{j}+\sum_{j=1}^{d}b_{j}p_{2}(x_{j})+\sum_{1\leq i<j\leq d}c_{ij}x_{i}x_{j}\)P\_\{2\}f(x)=1+\\sum\_\{j=1\}^\\{d\\}a\_j x\_j+\\sum\_\{j=1\}^\\{d\\}b\_j p\_2(x\_j)+\\sum\_\{1\\leq i<j\\leq d\\}c\_\\{ij\\}x\_i x\_j，其中系数\(a_j, b_j, c_ij\)由\(a_j=\langle f, p_1(x_j)\rangle_{L^2(\mu)}\)，\(b_j=\langle f, p_2(x_j)\rangle_{L^2(\mu)}\)，\(c_ij=\langle f, x_i x_j\rangle_{L^2(\mu)}\)给出。这些系数被组织到一个对称矩阵\(M(f)\in\mathbb{R}^{(d+1)\times(d+1)}M(f)\\in\\mathbb\\{R\\}^\\{(d+1)\\times(d+1)\\}\)中，其第一行和第一列由\(a_j\)填充，右下角的\(d\times d\)子矩阵具有对角线项\(3b_j\)和非对角线项\(5c_ij\)。关键性质是\(M(f)\)是密度二阶投影的等距表示：\(\left\lVert M(f)-M(g)\right\rVert_{\mathrm{F}}=\left\lVert P_{2}(f-g)\right\rVert_{L^{2}}\)。\\left\\lVert M(f)\\-M(g)\\right\\rVert\_\{\\mathrm\\{F\\}\\}=\\left\\lVert P\_\\{2\\}(f\\-g)\\right\\rVert\_\{L^\\{2\\}\\}。对于\([-1,1]^{d}\]\[-1,1\]^\\{d\\}上的观测值\(X_1, \\ldots, X_n\)，特征映射\(H_2: \\mathbb{R}^d \\to \\mathbb{R}^{(d+1)\\times(d+1)}\)H\_2:\\mathbb{R}^\\{d\\}\\to\\mathbb{R}^\\{(d+1)\\times(d+1)\\}被定义为一个矩阵，其第\((j,k)\)个元素是\(\\sqrt{w_j w_k} \\, L_j(X) L_k(X)\)，其中\(L_j\)是第j个勒让德多项式，\(w_j\)是\(L_j\)的\(L^2\)范数平方的倒数。则有\(\\mathbb{E}_f[H_2(X)] = M(f)\)。\\mathbb\\{E\\}\_f[H\_2(X)] = M(f)。

### 2.2 矩阵CUSUM
对于观测窗口\((s, e]\)\(s, e\]\)，定义投影均值矩阵为\(\Delta_{\\mathrm{CU}}^{s,e}(t) = \frac{1}{t-s} \sum_{i=s+1}^{t} H_2(X_i) - \frac{1}{e-t} \sum_{i=t+1}^{e} H_2(X_i)\)\\Delta\_\\{\\mathrm\\{CU\\}\\}^\\{s,e\\}(t) = \\frac{1}{t-s} \\sum\_\\{i=s+1\\}^\\{t\\} H\_2(X\_i) - \\frac{1}{e-t} \\sum\_\\{i=t+1\\}^\\{e\\} H\_2(X\_i)。在变化点\(\eta\)\(\\eta\)处，总体跳跃为\(D = M(f_1) - M(f_0)\)D = M(f\_1) - M(f\_0)，其中\(f_0, f_1\)是变化前后的密度。秩-\(r\)扫描统计量为\(\\widehat{W}_r^{s,e}(t) = \\left\\lVert (\\Delta_{\\mathrm{CU}}^{s,e}(t))_{(r)} \\right\\rVert_{\\mathrm{F}}\)，其中\((\\cdot)_{(r)}\)表示秩-\(r\)截断。总体目标函数\(a_b^{s,e}(t) = \\frac{e-b}{\\sqrt{e-s}} \\sqrt{\\frac{t-s}{e-t}}\)在\(t=b\)处达到最大值，形状为帐篷形。具体地，\(a_b^{s,e}(t) = \\begin{cases} \\dfrac{e-b}{\\sqrt{e-s}} \\sqrt{\\dfrac{t-s}{e-t}}, & t \\leq b \\\\ \\dfrac{b-s}{\\sqrt{e-s}} \\sqrt{\\dfrac{e-t}{t-s}}, & t > b \\end{cases}\)\(a\_b^\\{s,e\\}(t) = \\begin{cases} \\dfrac{e-b}{\\sqrt{e-s}} \\sqrt{\\dfrac{t-s}{e-t}}, & t \\leq b \\\\ \\dfrac{b-s}{\\sqrt{e-s}} \\sqrt{\\dfrac{e-t}{t-s}}, & t > b \\end{cases}\)（6）。因此，所有候选的总体矩阵共享相同的奇异向量和秩。系数在\(b\)之前递增，之后递减。更严格地说，\(\\left\\lVert \\Delta_{\\mathrm{CU}}^{s,e}(b) \\right\\rVert_{\\mathrm{F}}^{2} - \\left\\lVert \\Delta_{\\mathrm{CU}}^{s,e}(t) \\right\\rVert_{\\mathrm{F}}^{2} = \\begin{cases} \\dfrac{(e-b)(b-t)}{e-t} \\kappa^{2}, & t \\leq b \\\\ \\dfrac{(b-s)(t-b)}{t-s} \\kappa^{2}, & t > b \\end{cases}\)\\left\\lVert \\Delta\_\\{\\mathrm\\{CU\\}\\}^\\{s,e\\}(b) \\right\\rVert\_\\{\\mathrm\\{F\\}\\}^\\{2\\} - \\left\\lVert \\Delta\_\\{\\mathrm\\{CU\\}\\}^\\{s,e\\}(t) \\right\\rVert\_\\{\\mathrm\\{F\\}\\}^\\{2\\} = \\begin{cases} \\dfrac{(e-b)(b-t)}{e-t} \\kappa^\\{2\\}, & t \\leq b \\\\ \\dfrac{(b-s)(t-b)}{t-s} \\kappa^\\{2\\}, & t > b \\end{cases}\)（7）。这个精确的线性余量驱动了定位。图1（[链接](https://arxiv.org/html/2608.13922#S3.F1)）展示了一个\(d=100\)d=100依赖性变化示例中，秩二经验得分如何遵循总体帐篷形状。

图 1: 单个\(d=100\)d=100高斯Copula变化的总体和经验秩二阶密度CUSUM得分。坐标均值和边际分布未改变；只有前两个坐标的依赖性发生变化。
低秩步骤由一个确定性不等式控制。

###### 命题 3.1（低秩扰动）。
如果\(\widehat{A} = A + E\)\\widehat\\{A\\} = A + E，则\\(\\left\\lVert \\widehat{A}\_{(r)} - A \\right\\rVert\_{\\mathrm{F}} \\leq \\left\\lVert A - A\_{(r)} \\right\\rVert\_{\\mathrm{F}} + 2\\sqrt{2r}\\left\\lVert E \\right\\rVert\_{\\mathrm{op}}\\)。\\left\\lVert \\widehat\\{A\\}\\\_\\{(r)\\} - A \\right\\rVert\_\\{\\mathrm\\{F\\}\\} \\leq \\left\\lVert A - A\_\\{(r)\\} \\right\\rVert\_\\{\\mathrm\\{F\\}\\} + 2\\sqrt\\{2r\\}\\left\\lVert E \\right\\rVert\_\\{\\mathrm\\{op\\}\\}。因此，在一个秩\(\operatorname{rank}(D) \leq r\)\\operatorname\\{rank\\}\\(D\\) \leq r的单变化区间上，\\(\\left\\lVert \\bigl( \\widehat{\\Delta}\_{\\mathrm{CU}}^{s,e}(t) \\bigr)\_{(r)} - a\_b^{s,e}(t) D \\right\\rVert\_{\\mathrm{F}} \\leq c\_r\\sqrt{r} \\left\\lVert E\_{\\mathrm{CU}}^{s,e}(t) \\right\\rVert\_{\\mathrm{op}}\\)，其中\(c\_r = 2 + \\sqrt{2}\\)c\_r = 2 + \\sqrt\\{2\\}，\\(E\_{\\mathrm{CU}} = \\widehat{\\Delta}\_{\\mathrm{CU}} - \\Delta\_{\\mathrm{CU}}\\)E\_\\{\\mathrm\\{CU\\}\\} = \\widehat\\{\\Delta\\}\\\_\\{\\mathrm\\{CU\\}\\} - \\Delta\_\\{\\mathrm\\{CU\\}\\}。近似秩-\(r\)跳跃的近似尾项在附录C.1（[链接](https://arxiv.org/html/2608.13922#A3.SS1)）中陈述。

## 4 多变点与交叉拟合细化
### 4.1 种子化区间删除
固定一个最小尺度\(m\)。对于二进长度\(h \in \{m, 2m, 4m, \\ldots\\}\)h \in \\{m, 2m, 4m, \\ldots\\}，形成长度为\(h\)、起点间隔为\(h/2\)的区间；记该集合为\(\mathcal{I}\_m\)。在\(I = (s, e]\)I = (s, e]上，候选点限制在其中央半区\(\mathcal{T}\_I = \\{t : s + h/4 \\leq t \\leq e - h/4\\}\)T\_I = \\{t : s + h/4 \\leq t \\leq e - h/4\\}。令\(\widehat{b}\_I \in \operatorname\*{arg\\,max\\}\_{t \in \mathcal{T}\_I} \\widehat{W}\_r^{s,e}(t)\)，\(\widehat{S}\_I = \\widehat{W}\_r^{s,e}(\widehat{b}\_I)\)。\\widehat\\{b\\}\\\_I \\in \\operatorname\\*\\{arg\\,max\\}\\\_\\{t \\in \\mathcal\\{T\\}\\\_I\\} \\widehat\\{W\\}\\\_r^\\{s,e\\}(t)，\\qquad \\widehat\\{S\\}\\\_I = \\widehat\\{W\\}\\\_r^\\{s,e\\}(\\widehat\\{b\\}\\\_I)。算法1（[链接](https://arxiv.org/html/2608.13922#alg1)）中的区间删除过程反复选择超过阈值的最短区间，并将整个区间从后续递归中移除。移除一个区间而不是在\(\widehat{b}\_I\)\\widehat\\{b\\}\\\_I处分割，使得归纳过程清晰：一旦所选区间被确定为包含一个变化点且短于\(\Delta\)，它就不会移除另一个变化点。

算法 1 Seeded-LR-D2：种子化低秩二阶检测
1: 数据 \(X\_{1:n}\)，秩 \(r\)，最小尺度 \(m\)，阈值 \(\tau\)
2: 构建 \(\mathcal{I}\_m\) 并对所有 \(I \in \mathcal{I}\_m\) 计算 \((\widehat{b}\_I, \widehat{S}\_I)\)
3: 初始化活跃分量列表 \(\mathcal{C} \leftarrow \{(0, n]\}\)，输出 \(\widehat{\mathcal{B}} \leftarrow \varnothing\)
4: 当某个 \(I \in \mathcal{I}\_m\) 包含在 \(\mathcal{C}\) 的某个分量中且 \(\widehat{S}\_I > \tau\) 时
5:  选择最短的此类 \(I^* = (s^*, e^*]\)；将 \((I^*, \widehat{b}\_{I^*})\) 添加到 \(\widehat{\mathcal{B}}\)
6:  用非空分量 \((a, s^*]\) 和 \((e^*, c]\) 替换包含它的分量 \((a, c]\)
7: 结束循环
8: 返回 \(\widehat{\mathcal{B}}\)

### 4.2 交叉拟合局部细化
一个选定的区间\(I_k = (s_k, e_k]\)I\_k = (s\_k, e\_k]识别了一个变化点，但不一定提供最优速率。我们将其扩展为一个单变化窗口，并按奇偶性划分观测值。在引导折叠上，扫描窗口并在其最大化值处归一化秩-\(r\) CUSUM：\(\widehat{V}\_k = \dfrac{(\\widehat{\\Delta}\_{\\mathrm{CU}}^{\\mathrm{pilot}})\_{(r)}}{\\left\\lVert (\\widehat{\\Delta}\_{\\mathrm{CU}}^{\\mathrm{pilot}})\_{(r)} \\right\\rVert\_{\\mathrm{F}}}\)。\\widehat\\{V\\}\\\_k = \\dfrac{(\\widehat\\{\\Delta\\}\\\_\\{\\mathrm\\{CU\\}\\}^\\{\\mathrm\\{pilot\\}\\})\_\\{(r)\\}}{\\left\\lVert (\\widehat\\{\\Delta\\}\\\_\\{\\mathrm\\{CU\\}\\}^\\{\\mathrm\\{pilot\\}\\})\_\\{(r)\\} \\right\\rVert\_\\{\\mathrm\\{F\\}\\}}。在留出折叠上，投影\(Z_i = \langle H_2(X_i), \\widehat{V}_k \rangle\)Z\_i = \langle H\_2(X\_i), \widehat\\{V\\}\\\_k \rangle。不相交的外部锚块估计左、右投影均值\(\widehat{\mu}\_{L,k}\)和\(\widehat{\mu}\_{R,k}\)。在中心搜索区域上，定义\(Q_k(t) = \sum_{i \leq t} (Z_i - \widehat{\mu}\_{L,k})^2 + \sum_{i > t} (Z_i - \widehat{\mu}\_{R,k})^2\)，\(\widetilde{\eta}\_k \in \operatorname\*{arg\\,min\\}\_t Q_k(t)\)。Q\_k(t) = \sum\_\{i \leq t\} (Z\_i - \widehat{\mu\\}\\_\{L,k\})^2 + \sum\_\{i > t\} (Z\_i - \widehat{\mu\\}\\_\{R,k\})^2，\qquad \widetilde{\eta\\}\\_k \in \operatorname\\*\\{arg\\,min\\}\\_t Q\_k(t)。（8）
引导方向与留出噪声是独立的。条件于一个对齐良好的方向，问题简化为标量均值变化，其有效跳跃至少是\(\kappa_k\)的一个常数分数。

## 5 理论
本节假设每段密度相对于\(\mu\)是有界的，界为\(L\)。令\(\mathcal{G}\)为种子化集扫描的所有三元组\((s, t, e)\)的集合，并设\(\ell\_{\mathcal{G},\delta} = \log \dfrac{2(d+1)|\mathcal{G}|}{\delta}\)，\(\lambda\_m(\delta) = \sqrt{2L(1+d/2)\ell\_{\mathcal{G},\delta}} + \dfrac{8d\ell\_{\mathcal{G},\delta}}{\sqrt{m}}\)。\ell\_\\{\\mathcal\\{G\\},\\delta\\} = \log \\dfrac{2(d+1)|\\mathcal\\{G\\}|}{\delta}，\qquad \lambda\\_m(\delta) = \sqrt{2L(1+d/2)\ell\\_\\{\\mathcal\\{G\\},\\delta\\}} + \dfrac{8d\ell\\_\\{\\mathcal\\{G\\},\\delta\\}}{\sqrt{m}}。对于半重叠的二进区间，\(|\mathcal{G}| = O(n \log(n/m))\)。

###### 定理 5.1（均匀CUSUM与低秩控制）。
以至少\(1-\delta\)1-\delta的概率，\(\sup_{(s,t,e) \in \mathcal{G}} \\left\\lVert E\_{\\mathrm{CU}}^{s,e}(t) \\right\\rVert\_{\\mathrm{op}} \leq \lambda\_m(\delta)\)。\\sup\_\\{(s,t,e) \\in \\mathcal\\{G\\}\\} \\left\\lVert E\\\_\\{\\mathrm\\{CU\\}\\}^\\{s,e\\}(t) \\right\\rVert\\\_\\{\\mathrm\\{op\\}\\} \leq \lambda\\\_m(\delta)。在每个扫描的、包含一个至多秩-\(r\)变化点的区间上，\(\sup_{t \in \mathcal{T}\_I} \\left| \\widehat{W}\_r^{s,e}(t) - a_b^{s,e}(t) \\kappa \\right| \leq \varepsilon\_r\)，其中\(\varepsilon\_r = c\_r \sqrt{r} \lambda\_m(\delta)\)。\\sup\_\\{t \\in \\mathcal\\{T\\}\\_I\\} \\left| \widehat\\{W\\}\\_r^\\{s,e\\}(t) - a\\_b^\\{s,e\\}(t) \\kappa \\right| \leq \varepsilon\\\_r，\qquad \varepsilon\\\_r = c\\\_r \\sqrt{r} \\lambda\\\_m(\delta)。\(\lambda\_m\)\\lambda\\\_m的第一项是\(\asymp \sqrt{Ld \log(nd/\delta)}\)，并且不随区间长度增长，因为CUSUM权重的平方和为1。第二项是有界和校正当\(m \gg d \log(nd)\)m \gg d \log(nd)时为低阶项。

###### 定理 5.2（通过归纳的精确多变点恢复）。
假设\(m \leq \Delta/8\)m \leq \Delta/8，\(\operatorname{rank}(D\_k) \leq r\)\\operatorname\\{rank\\}(D\\\_k) \leq r，且阈值满足\(\sqrt{r} \lambda\_m(\delta) < \tau < \dfrac{\sqrt{\Delta}}{8\sqrt{2}} \kappa - \varepsilon\_r\)。\\sqrt{r} \lambda\\\_m(\delta) < \tau < \dfrac{\\sqrt{\\Delta}}{8\\sqrt{2}} \kappa - \varepsilon\\\_r。（9）
那么，在定理5.1（[链接](https://arxiv.org/html/2608.13922#S5.Thmtheorem1)）的事件上，Seeded-LR-D2返回恰好\(K\)个区间。它们与真实变点一一对应；每个选定区间恰好包含一个\(\eta\_k\)\\eta\\\_k且长度至多为\(\Delta/4\)\\Delta/4。特别地，其记录的最大值满足\(\|\\widehat{b}\_k - \eta\_k\| \leq \Delta/4\)\\|\\widehat\\{b\\}\\\_k - \eta\\\_k\\| \leq \Delta/4。证明在附录E（[链接](https://arxiv.org/html/2608.13922#A5)）中，遵循所要求的归纳法。在每个阶段：(i) 没有剩余变化点的区间得分低于\(\tau\)\\tau；(ii) 每个剩余变化点都有一个长度在\([\Delta/8, \Delta/4]\)[\\Delta/8, \\Delta/4]内的平衡隔离种子区间，其得分超过\(\tau\)\\tau。