{
  "id": "2203.07329",
  "version": "v1",
  "published": "2022-03-14T17:32:36.000Z",
  "updated": "2022-03-14T17:32:36.000Z",
  "title": "Randomized algorithms for Tikhonov regularization in linear least squares",
  "authors": [
    "Maike Meier",
    "Yuji Nakatsukasa"
  ],
  "categories": [
    "math.NA",
    "cs.NA"
  ],
  "abstract": "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 + \\lambda \\|x\\|^2_2$, where $A\\in\\mathbb{R}^{m\\times n}$ and $\\lambda>0$ is a regularization parameter, such that LSQR converges in $\\mathcal{O}(\\log(1/\\epsilon))$ iterations for $\\epsilon$ accuracy. We focus on the context where the optimal regularization parameter is unknown, and the system must be solved for a number of parameters $\\lambda$. 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 $\\lambda$. The complexity of solving for $N$ parameters is $\\mathcal{O}(mn\\log(\\max(m,n)) +N(\\min(m,n)^3 + mn\\log(1/\\epsilon)))$. Secondly, we introduce an algorithm that uses a sketch of size $\\mathcal{O}(\\text{sd}_{\\lambda}(A))$ for the case where the statistical dimension $\\text{sd}_{\\lambda}(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 $\\lambda_i$ in $\\mathcal{O}(mn\\log(\\max(m,n)) + \\min(m,n)\\,\\text{sd}_{\\min\\lambda_i}(A)^2 + Nmn\\log(1/\\epsilon))$ operations.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-03-14T17:32:36.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "65F08",
      "65F22",
      "68W20"
    ],
    "keywords": [
      "tikhonov regularization",
      "randomized algorithms",
      "optimal regularization parameter",
      "squares systems",
      "lsqr converges"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}