论文标题
在线性最小二乘中的Tikhonov正则化的随机算法
Randomized algorithms for Tikhonov regularization in linear least squares
论文作者
论文摘要
我们描述了两种算法，以根据草图有效地求解正则化线性最小二乘系统。该算法计算$ \ min \ | ax-b \ |^2_2 +λ\ | x \ | x \ |^2_2 $，其中$ a \ in \ Mathbb {r}^r}^{m \ times n} $和$λ> 0 $是正规化参数，使得lsqr参数，$ \ nog $ \ nog $ \ ymatim pogins in $ \ ymanc { $ε$精度的迭代。我们专注于最佳正则参数未知的上下文，并且必须为许多参数求解系统$λ$。我们的算法适用于不确定的$ m \ ll n $和过度确定的$ m \ gg n $设置。首先，我们提出了一种基于Cholesky的素描到至关节算法，该算法使用“部分精确”草图，并且仅需要一组$ n $正则化参数$λ$的草图。 $ n $参数的求解的复杂性是$ \ mathcal {o}（mn \ log（\ max（m，n）） + n（\ min（m，n）^3 + mn \ mn \ log（1/ε）））$。其次，我们介绍了一种算法，该算法使用大小$ \ Mathcal {o}的草图（\ text {sd}_λ（a））$ to统计尺寸$ \ text $ \ text {sd}_λ（a）\ ll \ min（m，n）$。我们提出的方案不需要计算革兰氏矩阵，在这种情况下，比现有算法更稳定。我们可以在$ \ Mathcal {o}中为$ n $的$ n $值解决（mn \ log（\ max（m，n）） + \ min（m，n）\，\ text {sd} _ {\minλ_i} _ {\minλ_i}（\minλ_i}（a）^2 + nmn \ log（a）
We describe two algorithms to efficiently solve regularized linear least squares systems based on sketching. The algorithms compute preconditioners for $\min \|Ax-b\|^2_2 + λ\|x\|^2_2$, where $A\in\mathbb{R}^{m\times n}$ and $λ>0$ is a regularization parameter, such that LSQR converges in $\mathcal{O}(\log(1/ε))$ iterations for $ε$ accuracy. We focus on the context where the optimal regularization parameter is unknown, and the system must be solved for a number of parameters $λ$. Our algorithms are applicable in both the underdetermined $m\ll n$ and the overdetermined $m\gg n$ setting. Firstly, we propose a Cholesky-based sketch-to-precondition algorithm that uses a `partly exact' sketch, and only requires one sketch for a set of $N$ regularization parameters $λ$. The complexity of solving for $N$ parameters is $\mathcal{O}(mn\log(\max(m,n)) +N(\min(m,n)^3 + mn\log(1/ε)))$. Secondly, we introduce an algorithm that uses a sketch of size $\mathcal{O}(\text{sd}_λ(A))$ for the case where the statistical dimension $\text{sd}_λ(A)\ll\min(m,n)$. The scheme we propose does not require the computation of the Gram matrix, resulting in a more stable scheme than existing algorithms in this context. We can solve for $N$ values of $λ_i$ in $\mathcal{O}(mn\log(\max(m,n)) + \min(m,n)\,\text{sd}_{\minλ_i}(A)^2 + Nmn\log(1/ε))$ operations.
