提出高效算法验证稀疏回归中矩阵的Kruskal秩，提升模型可识别性。
Efficient Algorithms for Verifying Kruskal Rank in Sparse Linear Regression and Related Applications
- 融合随机哈希与动态规划，统一处理不同代数域下的秩验证
- 运行时间近似达到理论下界，高概率保证正确性
- 对张量分解和深度学习中的噪声矩阵估计有实用价值
我们提出新颖的算法技术，高效验证稀疏线性回归、张量分解和潜变量模型中出现的矩阵的Kruskal秩。统一框架结合随机哈希与动态规划策略，适用于二元域、一般有限域及整数矩阵等场景。算法运行时间为 $/mathcal{O}ig(dk ullet (nM)^{ig floor k/2 ig floor}ig)$，并保证高概率正确性。主要贡献包括：跨代数设置的Kruskal秩验证统一框架；近乎匹配已知下界的严格运行时与高概率保证；在张量分解与深度学习中实现可识别性，尤其适用于噪声转移矩阵的估计。
原文摘要 · Abstract (English)
We present novel algorithmic techniques to efficiently verify the Kruskal rank of matrices that arise in sparse linear regression, tensor decomposition, and latent variable models. Our unified framework combines randomized hashing techniques with dynamic programming strategies, and is applicable in various settings, including binary fields, general finite fields, and integer matrices. In particular, our algorithms achieve a runtime of $\mathcal{O}\left(dk \cdot \left(nM\right)^{\lceil k / 2 \rceil}\right)$ while ensuring high-probability correctness. Our contributions include: A unified framework for verifying Kruskal rank across different algebraic settings; Rigorous runtime and high-probability guarantees that nearly match known lower bounds; Practical implications for identifiability in tensor decompositions and deep learning, particularly for the estimation of noise transition matrices.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。