Randomized flexible Krylov methods for $\ell_p$ regularization
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914089819701248 |
|---|---|
| author | Landman, Malena Sabaté Nakatsukasa, Yuji |
| author_facet | Landman, Malena Sabaté Nakatsukasa, Yuji |
| contents | The computation of sparse solutions of large-scale linear discrete ill-posed problems remains a computationally demanding task. A powerful framework in this context is the use of iteratively reweighted schemes, which are based on constructing a sequence of quadratic tangent majorants of the $\ell_2$-$\ell_1$ regularization functional (with additional smoothing to ensure differentiability at the origin), and solving them successively. Recently, flexible Krylov-Tikhonov methods have been used to partially solve each problem in the sequence efficiently. However, in order to guarantee convergence, the complexity of the algorithm at each iteration increases with respect to more traditional methods. We propose a randomized flexible Krylov method to alleviate the increase of complexity, which leverages the adaptability of the flexible Krylov subspaces with the efficiency of `sketch-and-solve' methods. A possible caveat of the mentioned methods is their memory requirements. In this case, one needs to rely instead on inner-outer schemes. In these scenarios, we propose a `sketch-to-precondition' method to speed up the convergence of each of the subproblems in the sequence. The performance of these algorithms is shown through a variety of numerical examples. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_11237 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Randomized flexible Krylov methods for $\ell_p$ regularization Landman, Malena Sabaté Nakatsukasa, Yuji Numerical Analysis 65F22, 65K10, 65F10, 68W20 The computation of sparse solutions of large-scale linear discrete ill-posed problems remains a computationally demanding task. A powerful framework in this context is the use of iteratively reweighted schemes, which are based on constructing a sequence of quadratic tangent majorants of the $\ell_2$-$\ell_1$ regularization functional (with additional smoothing to ensure differentiability at the origin), and solving them successively. Recently, flexible Krylov-Tikhonov methods have been used to partially solve each problem in the sequence efficiently. However, in order to guarantee convergence, the complexity of the algorithm at each iteration increases with respect to more traditional methods. We propose a randomized flexible Krylov method to alleviate the increase of complexity, which leverages the adaptability of the flexible Krylov subspaces with the efficiency of `sketch-and-solve' methods. A possible caveat of the mentioned methods is their memory requirements. In this case, one needs to rely instead on inner-outer schemes. In these scenarios, we propose a `sketch-to-precondition' method to speed up the convergence of each of the subproblems in the sequence. The performance of these algorithms is shown through a variety of numerical examples. |
| title | Randomized flexible Krylov methods for $\ell_p$ regularization |
| topic | Numerical Analysis 65F22, 65K10, 65F10, 68W20 |
| url | https://arxiv.org/abs/2510.11237 |