Growing the Rank Until It Stops Paying: SVD-Free Dinkelbach Optimization of the Nuclear-over-Frobenius Ratio

Filling in a partly observed matrix, such as an image with most pixels missing, usually means assuming the answer is "low rank," meaning it can be built from a few simple patterns. The user must then guess how many patterns to allow. Recent work avoids this guess by minimizing a ratio of two matrix norms, the nuclear norm (the sum of singular values) divided by the Frobenius norm (their root-sum-square). This ratio is a smooth stand-in for rank, and it does not change when the matrix is rescaled. It has given small but consistent gains in color image completion and robust tensor recovery. The catch is cost. Every iteration of these solvers computes a full singular value decomposition (SVD), which costs time cubic in matrix size. The authors themselves name "SVD-free" methods as the missing piece for high-resolution images and video.

We propose a solver with three parts. An outer loop applies Dinkelbach's method, a classical trick from fractional programming that turns a ratio into a sequence of subtraction problems. Each subtraction problem is made convex by linearizing the Frobenius term. A rank-growing conditional-gradient method then solves it, adding one rank-one piece at a time using only the top singular vector of a gradient, which Lanczos iteration finds cheaply. The rank is never specified. It stops growing at the first moment no new direction reduces the objective by more than it costs, and that moment can be checked from a single largest singular value. The result is a ratio-based completion method whose per-step cost is linear in the number of observed entries rather than cubic in matrix size. It stores only low-rank factors throughout, so the rank it ends with is a reported output rather than a chosen input.

Core Claim

The claim is that the parameter-free rank selection offered by the nuclear-over-Frobenius ratio can be kept while discarding the full SVD. The key structural fact is this. After Dinkelbach's substitution and a linearization of the Frobenius term, the subproblem at each outer step is a nuclear-norm problem plus a linear term. That is exactly the shape that projection-free, rank-growing solvers handle well.

Concretely, for observed entries $\Omega$ of a matrix $M$ and the operator $P_\Omega$ that keeps only those entries, the target problem is

$$\min_X \; \frac{\|X\|_*}{\|X\|_F} \quad \text{s.t.} \quad \|P_\Omega(X - M)\|_F \le \delta,$$

where $\delta$ is zero for noiseless data and is otherwise set from a noise estimate. A noise level is a physical quantity, unlike a rank or a regularization weight.

Dinkelbach's method keeps a scalar $q_k$ equal to the current ratio. It then attacks $\|X\|_* - q_k\|X\|_F$, which is the "nuclear minus Frobenius" objective of Quaternion Nuclear Norm minus Frobenius Norm Minimization for color image reconstruction. There, however, the weight is hand-fixed; here it is updated automatically.

Because $-q_k\|X\|_F$ is concave, we replace it by its tangent at the current iterate $X_k$. With $G_k = X_k/\|X_k\|_F$, each inner problem becomes

$$\min_X \; \|X\|_* - q_k \langle G_k, X\rangle + \frac{\rho}{2}\|P_\Omega(X - M) + \Lambda/\rho\|_F^2 .$$

Here $\rho$ and the multiplier $\Lambda$ come from an augmented Lagrangian treatment of the fidelity constraint. They are adapted by the solver, not tuned by the user. Denote by $h(X)$ the last two terms, the linear term plus the smooth fidelity penalty.

Standard optimality for nuclear-norm problems then gives a rank certificate. The current factored iterate is optimal for the inner problem, and no new rank-one atom is worth adding, exactly when

$$\sigma_1\big(\nabla h(X)\big) \le 1,$$

where $\sigma_1$ denotes the largest singular value.

The matrix $\nabla h(X)$ is a sparse matrix on $\Omega$ plus the low-rank term $q_k G_k$. A Lanczos matrix-vector product with it therefore costs $O(|\Omega| + (m+n)r)$ for an $m \times n$ matrix held at current rank $r$. The rank is decided by this certificate in the ratio's own units, not by a threshold, a budget, or a grid.

Relation to Prior Work

Two papers supply the objective and motivate the work. Quaternion Nuclear Norms Over Frobenius Norms Minimization for Robust Matrix Completion (QNOF) minimizes the ratio for color images represented as quaternion matrices. It reduces the problem to the singular values and solves it by ADMM, a splitting method that alternates between simpler subproblems. It requires a full quaternion SVD per iteration. Tensor robust principal component analysis via the tensor nuclear over Frobenius norm carries the same ratio to tensors through a full tensor SVD and proves local optimality of the true components. Neither uses Dinkelbach or any parametric transform, and neither scales beyond moderate image sizes. We keep their objective and replace their solver.

Two papers supply the method. The Dinkelbach iteration and its root-finding view of the ratio come from the fractional programming literature surveyed in Optimization problems and methods for resource allocation in wireless communications. The rank-growing conditional gradient with Lanczos top-singular-vector steps comes from Efficient Structured Matrix Rank Minimization, which grows the rank from one only as needed. That method, however, uses the convex nuclear norm with a penalty weight tuned by homotopy. Our contribution is to show that the ratio objective, after the Dinkelbach and linearization steps, fits this solver, and that the weight disappears.

Two further papers constrain the design. ADMM for Structured Fractional Minimization gives Dinkelbach-based ADMM (called FADMM-D) for single-ratio problems with an $O(1/\epsilon^3)$ complexity to approximate critical points. It is built on vector problems and reports sensitivity to its penalty schedule, which warns us that the augmented Lagrangian $\rho$ must be adapted rather than tuned.

We must also be honest about a point the fractional programming literature makes. Dinkelbach's fast convergence holds for concave-over-convex maximization. Our ratio is convex over convex, so each subproblem $\|X\|_* - q\|X\|_F$ is a difference of convex functions and is solved only to a stationary point. We therefore expect, and will only claim, convergence of an inexact Dinkelbach scheme to stationary points. Whether the fast outer convergence survives in practice is an empirical question we will measure.

Research Program

The first part is the algorithm. The outer loop updates $q_k$ to the current ratio. The middle loop re-linearizes $G_k$ and updates the multiplier $\Lambda$. The inner loop runs conditional-gradient steps on the factored iterate $X = UV^\top$. Each step finds the top singular pair of $\nabla h$ by Lanczos and checks the certificate. If the certificate fails, it appends the pair as a new rank-one atom and refines the factors locally, as in Efficient Structured Matrix Rank Minimization.

Atoms whose weight falls to zero during refinement are dropped, so the rank can shrink as well as grow. For color images we run on the real 4×4 block embedding of the quaternion matrix, where a block Lanczos of width four handles the repeated singular values. This keeps cross-channel coupling comparable to QNOF without a quaternion SVD.

The second part is analysis. We will prove that the outer ratio decreases monotonically under inexact inner solves. We will also prove that limit points are stationary for the constrained ratio problem, reusing majorization–minimization arguments of the kind used in ADMM for Structured Fractional Minimization. Finally, we will characterize when the certificate halts the rank at the true rank on random low-rank instances.

The third part is the empirical study described below. Its center is a single question: does the rank the method picks, without being told, match what an oracle-tuned method would pick, at a fraction of the cost?

Deep-network adapters such as LoRA are deliberately out of scope. There, stochastic gradients make the certificate noisy, and that would be a separate project.

Baselines

The naive reference is fixed-rank matrix completion by alternating least squares at a guessed rank. We run it at the true rank, as an oracle, and at ranks half and double that, to show what manual selection costs when the guess is wrong.

The strongest existing ratio method is QNOF's ADMM Quaternion Nuclear Norms Over Frobenius Norms Minimization for Robust Matrix Completion. It reports 20.46 dB PSNR on CSet12 with 80% of pixels missing, and a runtime of 4.96 seconds at 256×256. We will rerun it on the same masks and hardware. Beating it means matching its PSNR within 0.1 dB at 256×256 while running faster. More importantly, it means continuing to produce results at resolutions where its per-iteration SVD makes it impractical.

The strongest scalable competitor is nuclear-norm conditional gradient Efficient Structured Matrix Rank Minimization. It has the same Lanczos machinery and the same rank-growing behavior, but uses a weight $\lambda$. We give it the most generous possible treatment: $\lambda$ selected on held-out pixels from a 10-point grid, with the full grid's cost charged to it. Beating it means higher PSNR at equal wall-clock time, or equal PSNR without the grid.

The ablation that isolates our key ingredient is the identical solver with $q$ frozen at a constant $\alpha$. This is a conditional-gradient version of the nuclear-minus-Frobenius model of Quaternion Nuclear Norm minus Frobenius Norm Minimization for color image reconstruction. We sweep $\alpha$, and we also run it after rescaling the input by factors of 0.1 and 10. If a single well-chosen $\alpha$ matches the Dinkelbach update at every scale, the parametric update is not doing work.

Why not just…?

Why not just use nuclear-norm conditional gradient with a validated weight? This is the most serious threat, because it already grows rank on demand and avoids the SVD. The evidence against it is indirect. The ratio beat convex nuclear-norm minimization on CSet12 (20.46 dB versus 20.08 dB in Quaternion Nuclear Norms Over Frobenius Norms Minimization for Robust Matrix Completion). The tensor version showed larger exact-recovery regions than the convex tensor nuclear norm Tensor robust principal component analysis via the tensor nuclear over Frobenius norm. But those comparisons used fixed weights, not validated ones. If validated conditional gradient matches our PSNR and rank at equal total cost, including the grid, the proposal's value reduces to removing one hyperparameter, and we will report it that way.

Why not just run QNOF's ADMM with a truncated or randomized SVD? This is cheap and plausible. However, the truncation level is itself a rank cap, which reintroduces the manual choice we set out to remove. It also makes the proximal step of the ratio inexact in an uncontrolled way. We will run it with caps of 2×, 4×, and 8× the rank our method finds. If a loose cap gives QNOF's accuracy at our speed, our solver is unnecessary.

Why not just do gradient descent on factors with a generous rank and the ratio as a penalty? Overparameterized factorization is simple and fast, and the ratio might drive extra columns toward zero. But it needs a cap, the ratio is non-smooth at rank-deficient points, and nothing certifies that the surviving rank is meaningful. We will include it in the synthetic rank-recovery study. If its surviving rank matches ours as reliably, the certificate is the only remaining advantage.

Proposed Experiments

The decisive synthetic test uses random $m \times n$ matrices of known rank, with sampling rates and noise levels varied across a phase-transition grid. We measure three things: how often the selected rank equals the true rank, relative recovery error, and wall-clock time, as $n$ grows from $10^3$ to $10^5$ with fixed sampling density. Our method should show near-linear time growth in $|\Omega|$. QNOF should show cubic growth.

On images, we use CSet12 at 80% missing and compare against QNOF's reported 20.46 dB and 4.96 seconds. We also use the Kodak benchmark at 80% missing. There, the reported 23.81 dB for the nuclear-minus-Frobenius method with nonlocal patch grouping Quaternion Nuclear Norm minus Frobenius Norm Minimization for color image reconstruction belongs to a patch-based pipeline. We therefore compare against it only after placing our solver inside the same patch grouping. We then upsample to 1024, 2048, and 4K-sized inputs. No result for this setting is reported on Lacuna, so these curves are new measurements.

As a secondary test, we extend the method to robust principal component analysis on the five Kodak images with 20% sparse noise. The sparse part uses the standard weight $1/\sqrt{\max(m,n)}$, so the rank side remains parameter-free. The reference is TNF+'s reported 28.0875 dB average PSNR and 0.9537 SSIM Tensor robust principal component analysis via the tensor nuclear over Frobenius norm.

The proposal fails if any of three things happens. It fails if the selected rank varies by more than a few units across random initializations on the same instance. It fails if validated nuclear-norm conditional gradient matches it at equal total cost. It fails if the frozen-$\alpha$ ablation matches it across input rescalings, which would show the Dinkelbach update adds nothing over a tuned constant.