矩阵广义行列选择问题是数据科学中的基础问题之一，包含了矩阵子集选择问题的各种变形。传统的方法基于贪婪算法，且尚无对残差矩阵的2-范数上界的误差估计。我们采用交错多项式方法，提出了矩阵广义行列选择问题的多项式时间算法，并给出了残差矩阵的2-范数上界估计。与文献中已有的结果相比，我们的算法不仅能给出渐近最优的误差估计，而且所针对的矩阵更为广泛。

我们希望将交错多项式方法发展为数据科学领域中的系统性方法，从而改变该领域中一系列问题的面貌。本文正是实现这一愿景的关键一步。

    相关成果发表在《计算数学基础》（ Foundations of Computational Mathematics）上。

Publication: Foundations of Computational Mathematics

https://doi.org/10.1007/s10208-025-09719-5    

Authors:

Jian-Feng Cai
Department of Mathematics, The Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong SAR, China

LSEC, Inst. Comp. Math., Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100091, China

Email: jfcai@ust.hk

Zhiqiang Xu
LSEC, Inst. Comp. Math., Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100091, China

School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China

Email: xuzq@lsec.cc.ac.cn

Zili Xu（Corresponding author）
School of Mathematical Sciences, East China Normal University, Shanghai 200241, China

Shanghai Key Laboratory of PMMP, East China Normal University, Shanghai 200241, China

Key Laboratory of MEA, Ministry of Education, East China Normal University, Shanghai 200241, China

Email: zlxu@math.ecnu.edu.cn