线性 Sketch

线性摘要只保存频率向量经过固定投影后的坐标。每次更新等于给投影状态加一列，两个分片相加等于先合并频率再投影；解码器可以非线性，因为可合并性要求的是内部状态遵守同一代数，而不是最终估计也必须线性。

CountSketch 状态轨迹 ​

一行 CountSketch 选择桶哈希 $h:[n]\to [b]$ 与符号 $s:[n]\to \{\pm 1\}$，维护

更新 $(i,\mathrm{\Delta })$ 只改变 $y_{h(i)}$；估计坐标 $i$ 时计算 $s(i)y_{h(i)}$，碰撞项因随机符号而在期望中抵消，多行中位数再控制失败概率。

若流依次为 $(a,+4),(b,+2),(a,-1)$，最终 sketch 与一次性频率 $(3,2)$ 相同，体现更新顺序无关与 turnstile 兼容。两台机器采用同一 $h,s$ 时桶数组逐项相加正好是全局状态。

空间、种子与数值域 ​

显式矩阵可能有“摘要维数乘宇宙大小”个元素，远超状态预算。使用可由短种子生成各列的矩阵族时，实现保存该种子和 sketch 坐标，在更新时由 $i$ 生成所需列 $S{e}_i$。若生成一列需要扫描整个矩阵，空间虽省下，更新时间目标仍未达到。

两个站点若使用 $S_1,S_2$，直接相加 $S_{1}f+S_{2}g$ 不等于共享 $S(f+g)$。seed、哈希族版本、有限域或整数模数都属于合并协议。计数器位宽也必须覆盖可能的频率范围；整数溢出若不在预定模域内，会破坏线性等式。

随机保证还要说明流与查询是否在抽取 $S$ 后自适应。固定输入的高概率界不自动抵抗攻击者逐次查询并学习矩阵核；需要限制查询、刷新随机性或采用专门的鲁棒结构。

不是所有可合并摘要都线性 ​

Reservoir sampling 保存样本身份并按到达位置随机替换，滑动窗口依赖时间边界；两条具有相同最终频率向量的流可能需要不同状态，所以它们不能写成只依赖 $f$ 的 $Sf$。

Misra–Gries 有经过证明的 merge 过程，却要合并计数器后重新压缩，并非严格的向量加法。可合并性要求存在正确组合状态的运算；线性 sketch 因而是可合并摘要理路可合并摘要mergeable summary · mergeable sketch让分片流的有限状态在不读取原始数据时组合，并保持与集中处理相容的统计保证。中以向量加法组合状态的一类。

保证边界 ​

同一个 $Sf$ 可以服务点查询、范数估计或稀疏恢复，但 decoder 和维数各不相同。证明“更新与合并正确”只需线性等式，证明“小空间且精确”还需要碰撞、方差或下界分析；不能用前者替代后者。

通信下界归约理路通信下界归约范式Communication lower-bound reduction pattern · Communication reduction for lower bounds用固定长度的 INDEX 编码，把单遍精确不同元素计数的完整内存状态变成一次消息，并逐项保留错误、随机性和空间单位。可把 sketch 状态当作一条消息：Alice 对自己的更新得到 $S{f}_A$，把它发送给 Bob；Bob 加上 $S{f}_B$ 后运行 decoder，这正是单向通信协议理路单向通信复杂度One-way communication complexity限制 Alice 只向 Bob 发送一次消息，由 Bob 结合自身输入输出，并按消息 bit 数衡量代价。。若 decoder 能从合并状态恢复 Bob 指定的某个隐藏坐标，便可嵌入Indexing理路Indexing 通信问题Indexing communication problem · INDEX problemAlice 持有 n-bit 串、Bob 持有索引并要恢复对应 bit 的单向通信问题，是流式与摘要空间下界的标准母问题。并把其通信下界转成 sketch 位数下界。这里发送的是包含种子、数值精度与全部计数器的实际状态，而不只是矩阵行数；若 Bob 还需向 Alice 反馈，或双方矩阵不同，模拟就不再是同一单向协议。

一份可精算的稀疏解码器 ​

基追踪的稀疏恢复证书理路基追踪的稀疏恢复证书Basis pursuit recovery certificate · RIP certificate for sparse recovery · 基追踪与受限等距恢复从无噪声欠定观测建立 ℓ1 解码器，用完整分块证明和可精算的单纯形矩阵分开认证优化最优性与统一稀疏恢复。用七乘八和十五乘十六的固定实矩阵，把本页的线性更新与非线性解码接成完整算例：共享矩阵时先相加摘要，再以等式约束下的最小 ${\ell }_1$ 目标恢复满足稀疏约束的信号。其全支持受限奇异值与严格核条件负责恢复，更新同态只负责状态正确。该矩阵的单坐标更新最坏改变所有行，系数含平方根，实数坐标数也不是状态比特数；所以这个端点没有额外承诺小比特 streaming 空间或常数更新时间。两个分片各自稀疏还不够，调用恢复定理时须核对合并后向量的总支持。