arXiv:2601.11626math.NAcs.LG2026-01被引 1

提出可保证误差的矩阵压缩聚类方法,解决多矩阵合并压缩的可靠性问题。

Concatenated Matrix SVD: Compression Bounds, Incremental Approximation, and Error-Constrained Clustering

  • 基于谱界理论,建立矩阵拼接后奇异值分解误差上界
  • 设计增量式近似算法,无需构建完整拼接矩阵即可估测误差
  • 提供三种聚类算法,支持可控误差下的高效压缩

大规模矩阵集合广泛存在于现代机器学习、信号处理与科学计算中,通常通过拼接后进行截断奇异值分解(SVD)实现压缩,以实现参数共享和高效重建。然而,一个根本性问题尚未解决:在显式重构误差约束下,哪些矩阵可以安全地合并压缩?现有方法依赖启发式或架构特定分组,缺乏对最终SVD近似误差的理论保障。本文提出一种面向压缩的理论驱动聚类框架。分析建立了水平拼接矩阵的新谱界,从奇异值增长的下界推导出最优秩-$r$ SVD重构误差的全局上界。第一个界源于块扩展下的Weyl型单调性,第二个界利用增量残差的奇异值,获得更紧的逐块保证。进一步提出一种基于增量截断SVD的高效近似估计器,可在不构造完整拼接矩阵的情况下追踪主导奇异值。据此设计了三种聚类算法,仅当预测联合SVD压缩误差低于用户指定阈值时才合并矩阵。算法在速度、可证明精度与可扩展性之间权衡,实现带显式误差控制的压缩感知聚类。

原文摘要 · Abstract (English)

Large collections of matrices arise throughout modern machine learning, signal processing, and scientific computing, where they are commonly compressed by concatenation followed by truncated singular value decomposition (SVD). This strategy enables parameter sharing and efficient reconstruction and has been widely adopted across domains ranging from multi-view learning and signal processing to neural network compression. However, it leaves a fundamental question unanswered: which matrices can be safely concatenated and compressed together under explicit reconstruction error constraints? Existing approaches rely on heuristic or architecture-specific grouping and provide no principled guarantees on the resulting SVD approximation error. In the present work, we introduce a theory-driven framework for compression-aware clustering of matrices under SVD compression constraints. Our analysis establishes new spectral bounds for horizontally concatenated matrices, deriving global upper bounds on the optimal rank-$r$ SVD reconstruction error from lower bounds on singular value growth. The first bound follows from Weyl-type monotonicity under blockwise extensions, while the second leverages singular values of incremental residuals to yield tighter, per-block guarantees. We further develop an efficient approximate estimator based on incremental truncated SVD that tracks dominant singular values without forming the full concatenated matrix. Therefore, we propose three clustering algorithms that merge matrices only when their predicted joint SVD compression error remains below a user-specified threshold. The algorithms span a trade-off between speed, provable accuracy, and scalability, enabling compression-aware clustering with explicit error control.

矩阵压缩SVD聚类误差控制

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。