Warm-Started Newton Thresholding for Quaternion Low-Rank Recovery

Color images can be stored as quaternion matrices. Quaternions are four-part numbers whose multiplication is order-dependent, and storing each pixel as $0 + Ri + Gj + Bk$ keeps the red, green and blue channels coupled rather than treating them separately. This representation now drives some of the best low-rank color restoration methods. Their solvers alternate between a data-fitting step and a "shrink the singular values" step. The second step needs a full quaternion singular value decomposition (QSVD) at every iteration, which costs $O(n^3)$, and the authors of these methods name it as the obstacle to high-resolution and video use. We propose to remove the QSVD by computing the shrinkage step as a matrix function built only from quaternion matrix inversions and multiplications.

The idea extends Cai and Osher's SVD-free thresholding for real matrices in two ways the real-valued version never needed. First, it handles the non-convex, data-dependent shrinkage rules that quaternion methods use. Second, the inner iteration is warm-started across the outer solver's steps, so that after the first few steps each shrinkage costs only one or two Newton steps. If this works, quaternion nuclear-norm restoration becomes a sequence of dense matrix multiplications that map well onto GPUs, and its cost scales well past 256×256 images.

Core Claim

Three facts together make QSVD unnecessary inside the outer solver.

First, the polar factorization $Y = WZ$, with $W$ having orthonormal columns and $Z$ Hermitian positive semidefinite, can be computed for a quaternion matrix by the Newton iteration $W_{k+1} = \tfrac12(W_k + W_k^{-*})$, where $^{*}$ is the quaternion conjugate transpose. Each step needs only a quaternion matrix inverse.

Second, a rational function with real coefficients, applied to a Hermitian quaternion matrix, is unambiguous despite non-commutativity. Real scalars commute with every quaternion, so $p(Z) = U\,p(\Sigma)\,U^*$ holds without ever forming $U$. Spectral projectors such as $\tfrac12(I + \mathrm{sign}(Z - \tau I))$ can then be obtained by Newton sign iterations, and any shrinkage rule that is piecewise rational in each singular value can be assembled from them.

Third, the scalar summaries these regularizers depend on are available for free. The nuclear norm is $\mathrm{tr}(Z)$, and the Frobenius norm needs no factorization. The QNOF ratio $\|X\|_*/\|X\|_F$ and the QNMF difference $\|X\|_* - \alpha\|X\|_F$ can therefore be evaluated, and their proximal steps parameterized, without singular values.

On top of these facts we add the warm start. The ADMM iterates $Y_t$ change little between outer steps, so $W_{t-1}$ is already close to the polar factor of $Y_t$. We claim that an inexact inner solve, stopped once its error falls below a schedule tied to the ADMM primal and dual residuals, preserves the reconstruction quality of the QSVD-based methods at a fraction of their wall-clock time. We also claim the advantage grows with image size.

Where This Sits

The proposal is motivated by three quaternion restoration methods that pair an ADMM solver with a per-iteration QSVD. ADMM, the alternating direction method of multipliers, is an augmented-Lagrangian scheme that splits a constrained problem into alternating subproblems plus a multiplier update. Quaternion Nuclear Norms Over Frobenius Norms Minimization for Robust Matrix Completion introduces the scale-invariant QNOF regularizer. It reduces the quaternion proximal problem to real singular value shrinkage, computes that shrinkage with QSVD, and explicitly calls for "SVD-free" methods to reach 4K imagery. Quaternion Nuclear Norm minus Frobenius Norm Minimization for color image reconstruction derives a closed-form QNMF shrinkage that penalizes large singular values less than small ones. It names QSVD as "the primary bottleneck." Non-Local Robust Quaternion Matrix Completion for Large-Scale Color Images and Videos Inpainting groups similar patches into very low-rank quaternion matrices. It runs a QSVD per group and notes that runtime grows with the number of groups. We keep their models and their ADMM outer loops and replace only the shrinkage computation.

The proposal reuses its central technique from Fast singular value thresholding without singular value decomposition. That paper computes real singular value thresholding through a polar Newton iteration and a rational projection, and reports roughly a sixfold speedup inside an augmented Lagrangian solver on dense matrices. It is real-valued only, handles only convex soft-thresholding, and restarts each inner solve from scratch. We change all three.

The SVT/Uzawa view in A Singular Value Thresholding Algorithm for Matrix Completion tells us why the outer loop tolerates inexact shrinkage: it is a dual ascent, and errors in the primal step enter as bounded perturbations. Generalized Singular Value Thresholding shows that proximal maps of lower-bounded non-convex penalties are monotone in each singular value. That monotonicity is what lets us build the generalized rules from ordered spectral projectors.

Two prior lines of work constrain the design. Efficient quaternion CUR method for low-rank approximation to quaternion matrix avoids QSVD by sampling actual rows and columns. It is a one-shot approximation that was never placed inside an ADMM loop, and its authors flag degradation when the sampled rows and columns are mostly missing. That is exactly the 80%-missing regime we target. Deeply Learned Robust Matrix Completion for Large-scale Low-rank Data Recovery replaces SVD with a fixed-rank factorization $LR^T$ and concedes that it needs the rank in advance. Our approach thresholds and does not truncate, so the rank is discovered rather than fixed.

The quaternion linear algebra pieces come from two papers. Gl‐QFOM and Gl‐QGMRES shows that working natively in quaternions, rather than on the 4×-larger real block form, saves about three-quarters of the cost. Generalizing Frobenius inversion to quaternion matrices supplies block-inversion identities that hold despite non-commutativity. We use both inside the Newton steps, and Gl-QGMRES also handles the linear deblurring subproblem that QNMF currently solves directly.

Research Program

The first component is a quaternion scaled-Newton polar solver. For a rectangular $Y \in \mathbb{H}^{m\times n}$ with $m \ge n$, we first reduce to a square $n\times n$ problem with a quaternion QR factorization. Newton steps then run with determinant-free norm scaling, using $\gamma_k = (\|W_k^{-1}\|_F/\|W_k\|_F)^{1/2}$, to get fast early convergence. Inverses are computed by quaternion LU or by recursive Frobenius block inversion.

We will prove that the iteration stays inside the structured class of matrices that correspond to quaternion matrices under the real block representation. This gives a clean link to the real-valued convergence theory, since quadratic convergence then follows from the real case. We will also record the flop ratios. A native quaternion matrix product costs 16 real products of the same size, compared with 64 for the 4×-larger real representation and about 32 for the 2×-larger complex adjoint form.

The second component builds generalized thresholds from spectral projectors. Soft-thresholding uses the Cai–Osher form $D_\tau(Y) = Y - W\,P_\tau(Z)$. For QNMF and QNOF, whose shrinkage amount depends on $\|X\|_F$ and $\|X\|_*$, we compute these scalars from $\mathrm{tr}(Z)$ and $\|Y\|_F$. We then express the resulting per-singular-value rule as a real-coefficient piecewise-rational function of $Z$, built from one or two shifted sign iterations. Where the exact rule is not rational, we use a low-degree rational approximation with a certified error, and that error feeds into the inexactness budget.

The third component is warm-started inexact ADMM. At outer step $t$, the polar iteration starts from $W_{t-1}$, rescaled. It stops when $\|W_k^*W_k - I\|_F$ falls below $\eta_t$, where $\eta_t$ is a summable sequence proportional to the current ADMM residuals. We will adapt standard inexact augmented-Lagrangian arguments to show that summable proximal errors preserve the convergence guarantees the original papers claim for their schemes. We will also measure how many Newton steps are actually used per outer step.

The fourth component is a scope check on dual quaternions. Dual quaternions are eight-part numbers that represent rigid motions, and they introduce non-invertible "pure dual" entries. We will test whether the Sylvester-equation device in LU decomposition and generalized Autoone-Takagi decomposition of dual matrices and their applications carries the Newton inverse through the dual part. The same authors leave quaternion LU over dual quaternions open, so this is an exploratory extension and not a promised result.

Baselines

The strongest existing method is QNOF with per-iteration QSVD inside ADMM. On CSet12 inpainting with 80% missing pixels it reports 20.46 dB PSNR, against 20.37 dB for QNMF and 20.08 dB for QNNM. It converges in 4.96 seconds on a 256×256 image, where QSNM needed over 14 seconds. We will rerun it from the released formulation on our hardware, with identical masks, initialization, ADMM penalty and outer-iteration budget. Our method keeps every outer parameter fixed and changes only the shrinkage computation. Beating QNOF means matching its PSNR to within 0.05 dB on CSet12 at 80% missing while cutting wall-clock time, by at least 3× at 1024×1024 and by more at larger sizes.

QNMF is the second model we accelerate. It reports 28.06 dB on Kodak denoising at $\sigma=60$, against 27.90 for CBM3D and 27.95 for QWNNM, and 23.81 dB for its non-local variant at 80% missing, against 19.71 for TRPCA. Our accelerated QNMF must reproduce those PSNRs within 0.05 dB.

We will also run QMCUR placed inside the same ADMM loop as the shrinkage approximator, with both length-based and uniform sampling. This is the existing SVD-avoiding quaternion competitor. No reported result found on Lacuna for QMCUR inside an iterative completion solver, so we establish this number ourselves. For the non-local setting, we will run partial-QSVD and fixed-rank $LR^T$ factorization baselines on the same patch groups. Each gets the oracle rank and then a misspecified rank, which reflects the known weakness reported in Deeply Learned Robust Matrix Completion for Large-scale Low-rank Data Recovery.

The naive reference point is independent per-channel real SVT with the Cai–Osher solver. It is cheap, but it discards the cross-channel coupling. The gap between it and the quaternion methods measures what the quaternion representation buys.

Two ablations isolate our ingredients. The first is the same algorithm with cold-started inner solves, which isolates the warm start. The second is the same warm-started algorithm run on the complex adjoint representation with standard complex BLAS, which isolates native quaternion arithmetic. All methods share hardware, precision and stopping criteria.

Why not just…?

Why not just run Cai–Osher on the complex adjoint matrix? This is the most serious threat. The complex adjoint form is exactly equivalent to the quaternion matrix, and mature complex GPU libraries may outrun a custom quaternion kernel despite doing roughly twice the flops. We will not argue around this. The algorithmic contributions are threshold-as-matrix-function for non-convex rules and the warm-started inexact loop, and both apply in any representation. The complex-adjoint ablation decides which arithmetic to ship. If complex wins in wall-clock time, we report that and keep the quaternion version only for its memory advantage.

Why not just use QMCUR or randomized low-rank approximation inside ADMM? Sampling methods approximate the matrix but do not compute a threshold, so the rank must be chosen. QMCUR's authors already note weaker accuracy under noise and unaddressed failure when the sampled rows and columns are mostly missing. Our in-loop QMCUR baseline at 50–90% missing will show whether this costs PSNR. If QMCUR matches quality at equal time, our method's remaining case rests on not needing a rank.

Why not just use partial QSVD, given that grouped patches are very low-rank? Non-Local Robust Quaternion Matrix Completion for Large-Scale Color Images and Videos Inpainting reports that grouping concentrates 98% of spectral energy in 2% of the singular values, and Cai and Osher concede that Lanczos-type partial SVD stays competitive at very small rank. We expect partial QSVD to win on small patch groups. We will report the crossover in matrix size and rank and not claim uniform superiority.

Proposed Experiments

We will benchmark inpainting on CSet12 and Kodak at 50%, 70%, 80% and 90% missing pixels, Gaussian denoising on Kodak and McMaster at $\sigma \in \{30, 60\}$, and deblurring with Gl-QGMRES for the linear subproblem. Metrics are PSNR, SSIM, wall-clock time, and Newton steps per outer iteration.

The decisive scaling check upsamples or crops Set27 and Kodak images to 512, 1024, 2048 and 3840×2160 and plots time against size for every method. The claim fails if the speedup over QSVD-ADMM does not grow with size. It also fails if warm starting does not drive inner steps to one or two after the first few outer iterations.

The second decisive check is quality parity. If PSNR drops by more than 0.1 dB relative to the QSVD versions at any missing rate, the inexactness schedule is too loose, and we will report the tradeoff curve instead of a single operating point.

The third check is the representation ablation, which settles the complex-adjoint question.

The final check applies the method to the non-local video setting of, where we expect a mixed result. It will show for which patch-group sizes Newton thresholding should replace partial QSVD.