Accurate Solution of Structured Least Squares Problems via Rank-Revealing Decompositions
Accurate Solution of Structured Least Squares Problems via Rank-Revealing Decompositions
复制标题
DOI：
10.1137/12088642x
复制
发表时间：
2013-07
期刊：
影响因子：
--
通讯作者：
N. Castro-González;Johan Ceballos;F. Dopico;Juan M. Molera
中科院分区：
文献类型：
--
作者：
N. Castro-González;Johan Ceballos;F. Dopico;Juan M. Molera
最小二乘问题$\min_x \|b - Ax\|_2$在应用中经常出现，其中矩阵$A\in \mathbb{C}^{m\times n}$ （$m\geq n$）具有一些特殊的结构。多项式数据拟合是产生高度结构化矩阵的一个众所周知的问题实例，但也存在许多其他的例子。通常，结构化矩阵具有巨大的条件数$\kappa_2 (A) = \|A\|_2 \, \|A^\dagger\|_2$ （$A^\dagger$是$A$的Moore—Penrose伪逆），因此标准算法无法计算最小二乘问题的精确最小二范数解。在这项工作中，我们引入了一个框架，使我们能够准确地计算许多类结构化最小二乘问题的最小二范数解，即误差$\| \widehat{x}_0 - x_0 \|_2 / \|x_0 \|_2 = O({\tt u})$，其中${\tt u}$是单位舍入，独立于大多数向量$b$的$\kappa_2 (A)$的大小。这些精确计算的成本是$O(n^2 m)$ flop，也就是说，与标准算法的成本大致相同……
Least squares problems $\min_x \|b - Ax\|_2$ where the matrix $A\in \mathbb{C}^{m\times n}$ ($m\geq n$) has some particular structure arise frequently in applications. Polynomial data fitting is a well-known instance of problems that yield highly structured matrices, but many other examples exist. Very often, structured matrices have huge condition numbers $\kappa_2 (A) = \|A\|_2 \, \|A^\dagger\|_2$ ($A^\dagger$ is the Moore--Penrose pseudoinverse of $A$) and therefore standard algorithms fail to compute accurate minimum 2-norm solutions of least squares problems. In this work, we introduce a framework that allows us to compute minimum 2-norm solutions of many classes of structured least squares problems accurately, i.e., with errors $\| \widehat{x}_0 - x_0 \|_2 / \|x_0 \|_2 = O({\tt u})$, where ${\tt u}$ is the unit roundoff, independently of the magnitude of $\kappa_2 (A)$ for most vectors $b$. The cost of these accurate computations is $O(n^2 m)$ flops, i.e., roughly the same cost as standard algorithm...