Tight Majorizations and Convergence Rates of Nuclear Norm Minimization IRLS

Christian Kümmerle; Tomas Masak; Dominik Stöger

cs.LGAug 24, 2026

Tight Majorizations and Convergence Rates of Nuclear Norm Minimization IRLS

Authors: Christian Kümmerle, Tomas Masak, Dominik Stöger

Organizations: School of Data, Mathematical, and Statistical Sciences, Department of Computer Science & Institute of Artificial Intelligence, University of Central Florida, Oviedo, FL 32816, USA · Institute for Statistics and Mathematics, Wirtschaftsuniversität Wien, 1020 Vienna, Austria · Department of Mathematics, KU Eichstätt-Ingolstadt, 85049 Ingolstadt, Germany

Abstract

Iteratively reweighted least squares (IRLS) methods constitute a natural approach to nuclear norm minimization, but their convergence rates and the role of the weight operator have remained poorly understood. This paper establishes sharp convergence rates for IRLS methods for constrained nuclear norm minimization in low-rank recovery. A central ingredient is a new majorization analysis for the smoothed nuclear norm: we prove that the harmonic-mean weight operator defines a valid global quadratic majorizer. Furthermore, we show that this weight operator is optimal within the family of power-mean weights, clarifying why it improves over classical one-sided reweighting schemes that use only row- or column-space information. Under a Schatten-1 null space property, we prove global linear convergence of IRLS algorithms using a variety of weight operators, including the harmonic-mean weights. For IRLS with harmonic-mean weights, we prove a dimension-independent, locally linear convergence rate. We provide a counterexample showing that this dimension-independent local rate cannot in general be obtained for IRLS algorithms using one-sided weight operators, which predominate in the literature. Numerical experiments corroborate the theoretical results and illustrate the practical advantage of harmonic-mean reweighting across square, rectangular, and adversarially initialized recovery problems.

Figures & tables

Figure 1: Smoothed nuclear norm gap

\mathcal{J}_{\varepsilon_{k}}(\mathbf{X}^{(k)})-\left\lVert\mathbf{X}_{\star}\right\rVert_{\ast}

of IRLS iterates for harmonic, left-sided, right-sided, and arithmetic mean weight operators. The rank-

2

ground truth

\mathbf{X}_{\star}\in\R^{140\times 140}

and the

m=2520

rank-one measurements are generated using independent

\mathcal{N}(0,1)

entries.

Reference	Weight	Global guarantee	Local / distinguishing result
Sparse recovery ( $\ell_{1}$ ): benchmark
Daubechies et al. (2010)	entrywise	conv. under NSP; no rate	local linear rate; basin $O(\mathbf{x}_{\star}^{\operatorname{min}})$
Kümmerle et al. (2021)	entrywise	linear rate, $1-\frac{C}{\eta_{1}d}$	arbitrary initialization
Low-rank recovery (nuclear norm): direct comparison
Fornasier et al. (2011) ; Mohan and Fazel (2012)	one-sided	conv. under NSP; no rate	no local rate established
Cai and Li (2017)	one-sided	conv. under RIP; no rate	approx. rank, noise stability

Table 1: IRLS convergence results at the convex endpoint

p=1

: the sparse

\ell_{1}

benchmark and the direct nuclear-norm comparison. The final row records the harmonic-mean specialization of this paper.

Figure 2: The nuclear norm of ( 9 ) from Example 1 . Left : The smoothed nuclear norm

\mathcal{J}_{\varepsilon}

for

\varepsilon=0.8,0.5,0.2

and

0.1

. Right : The left-sided, right-sided, and harmonic-mean surrogates of

\mathcal{J}_{0.5}

t_{0}=1/2

. The next step of the algorithm with

\varepsilon

reduced to

0.2

is also indicated.

\displaystyle\mathbf{X}^{(k)}

\displaystyle:=\argmin_{\mathbf{Z}\in\R^{d_{1}\times d_{2}}}\ \langle\mathbf{Z},W^{(k)}(\mathbf{Z})\rangle_{F}\;\text{ subject to }\;\mathcal{A}(\mathbf{Z})=\mathbf{y}.

(12)

Algorithm 1 MatrixIRLS for Nuclear Norm Minimization

Figure 3: Smoothed nuclear norm gap

\mathcal{J}_{\varepsilon_{k}}\left(\mathbf{X}^{(k)}\right)-\left\lVert\mathbf{X}_{\star}\right\rVert_{\ast}

of IRLS iterates

\mathbf{X}^{(k)}

for different weight operator variants (harmonic, left-sided, right-sided, arithmetic) across matrix dimensions

d\in\{30,60,90,110,140\}

, rank-

2

ground truth

\mathbf{X}_{\star}\in\R^{d_{1}\times d_{2}}

, random Gaussian rank-one measurements with linear scaling.

Figure 4: Successive decrease-factor trajectories for the standard initialization

\mathbf{X}^{(0)}

in the random Gaussian rank-one measurement setup, shown for

d\in\{30,60,140\}

. The color pattern and variant order match Figure 3 : harmonic (blue), left-sided (green), right-sided (red), arithmetic (orange). For

d=60

and

d=140

, only iteration indices

0

through

150

are displayed.

Figure 5: Smoothed nuclear norm gap trajectories

\mathcal{J}_{\varepsilon_{k}}\left(\mathbf{X}^{(k)}\right)-\left\lVert\mathbf{X}_{\star}\right\rVert_{\ast}

for the tall rectangular recovery experiment with standard initialization and dimensions

d\in\{20,40,80\}

. In each panel, a rectangular ground truth

\mathbf{X}_{\star}\in\R^{4d\times d}

of rank

r=2

is recovered from

m=4.5r(d_{1}+d_{2})

random Gaussian rank-one measurements.

Figure 6: Successive decrease-factor trajectories

\mu(k)

of eq. 40 for the tall rectangular recovery experiment with standard initialization, shown for

d\in\{20,40,80\}

and rank

r=2

ground truth

\mathbf{X}_{\star}\in\R^{4d\times d}

. Each trajectory ends once the respective variant terminates or the maximal iteration count of

500

is reached.

Figure 7: Reciprocal first-algorithmic contraction gaps

1/(1-\mu(0))

(for initial), measuring the transition from

\mathbf{X}^{(0)}

\mathbf{X}^{(1)}

, for the extended recurrence initialized by

(\mathbf{X}^{(-1)},\varepsilon_{-1})

and the resulting

W^{(0)}

, across dimensions

d\in\{25,30,40,50,60,70,80,90,100,110,120,130,140\}

in the square random Gaussian rank-one measurement setup with rank-

2

ground truth and linear measurement scaling; five terminal iteration average of

1/(1-\mu(k))

for the harmonic-mean variant. Median values across

10

seeds with

25\%

and

75\%

quantiles.

Figure 8: Selected trajectory plots of IRLS variants with different smoothing parameter update rules at dimension

d=60

with rank-

2

ground truth and Gaussian rank-one measurements. Left: Objective gap

\left|\mathcal{J}_{\varepsilon_{k}}\left(\mathbf{X}^{(k)}\right)-\left\lVert\mathbf{X}_{\star}\right\rVert_{\ast}\right|

vs. iteration

k

for

C=3.0

. Right: Analogous experiment with oversampling factor of

C=4.0

Figure 9: Phase transition experiment for nuclear norm MatrixIRLS with harmonic-mean weight operator, showing distribution of relative Frobenius errors across

12

problem instances for different oversampling factors

C

and different smoothing parameter update rules.

$C$	Update rule / solver	$r_{\mathrm{env}}^{(1)}$	$r_{\mathrm{env}}^{(10)}$	$r_{\mathrm{env}}^{(\tilde{k})}$	$\tilde{k}$	$k_{\tau}$	Runtime [s]
$3.0$	$\ell_{1}$ -tail	$39$	$21$	$15$	$359$	$269$	$18.39$
$3.0$	$\ell_{2}$ -tail	$29$	$15$	$12$	$726$	$585$	$27.30$
$3.0$	$\ell_{\infty}$ -tail	$2$	$2$	$2$	$191$	–	–
$3.0$	SCS	–	–	–	–	–	$25.37$
$4.0$	$\ell_{1}$ -tail	$38$	$22$	$19$	$57$	$43$	$4.88$
$4.0$	$\ell_{2}$ -tail	$29$	$17$	$14$	$62$	$47$	$3.53$

Table 2: Envelope ranks and computational effort for the representative

d=100

, rank-

2

, seed-

42

smoothing-parameter experiment with the harmonic mean weight operator. For IRLS, runtime is the median cumulative solver time to reach the objective-gap threshold

\tau=10^{-5}

over 5 timing repetitions after 1 warmup. For SCS , runtime is the solver-reported numerical solve time; CVXPY canonicalization and SCS setup are excluded. A dash denotes a quantity that is not applicable or an objective-gap threshold not reached before termination.

Nuclear Norm Minimization

Nuclear norm minimization uses the sum of singular values to find low-rank matrices or tensors from incomplete or noisy data.

See all 15 papers

Sep 21, 2026

Guaranteed Low-Rank Tensor Recovery from Modewise Measurements via Normalized Block-Weighted Riemannian Gradient Descent

We consider the recovery of low-multilinear-rank tensors from linear measurements and propose an adaptive block-weighted modewise Riemannian gradient descent method. The method combines memory-efficient modewise measurements with a normalized adaptive weighting strategy for the core and factor components of the Riemannian gradient. The weighting improves convergence without increasing the multilinear-rank bound of the search direction or the size of the reduced core used for retraction. Under the tensor restricted isometry property and a suitable initialization, we establish local linear convergence and derive sampling guarantees for sub-Gaussian and subsampled orthogonal with random sign (SORS) measurements. Numerical experiments on synthetic low-Tucker-rank tensors show that the proposed method reduces iteration counts and computational time while maintaining reliable recovery performance, especially near the recovery threshold and for structured SORS measurements.

Yushi Zhou, Feng Zhang

School of Mathematics and Statistics, Southwest University, Chongqing, China.

Riemannian Optimization Tensor Decomposition

Ask PDF

Aug 29, 2026

Sharp Restricted Isometry Thresholds for Global Minima of Rank-Restricted Matrix LASSO

We determine the sharp restricted isometry threshold for recovery at global minima of the rank-restricted matrix LASSO. For target rank

r_{\star}

, if the rank-

k

RIP constant satisfies

δ<δ_{\mathrm{sharp}}(k/r_{\star})

, where

δ_{\mathrm{sharp}}(t)=t/(4-t)

for

0<t<4/3

and

δ_{\mathrm{sharp}}(t)=\sqrt{(t-1)/t}

for

t\ge4/3

, then every global minimizer has Frobenius error

\lesssim\sqrt{r_{\star}}λ

for all

λ\gtrsim\|\mathcal{A}^{*}(ξ)\|_{\mathrm{op}}

and at every search rank

r\ge r_{\star}

. The constants depend only on the RIP constant and

t=k/r_{\star}

, and in particular are independent of the search rank. When the rank restriction is inactive, the result specializes to the ordinary convex matrix LASSO. We also obtain the analogous results for sparsity-restricted vector LASSO. Conversely, we show that the threshold

δ<δ_{\mathrm{sharp}}(k/r_{\star})

cannot be improved, due to the existence of counterexamples whose global minimizers fail to recover the ground truth.

Richard Y. Zhang

Department of Electrical and Computer Engineering, University of Illinois Urbana–Champaign, Urbana, IL 61801 USA

Matrix Optimization Sparse Recovery Nonconvex Optimization

Ask PDF

Sep 15, 2026

Near-Optimal Nonconvex Matrix Completion

We study nonconvex methods for matrix completion, the problem of recovering a low-rank matrix from a subset of its entries. Convex methods achieve sample complexity linear in the matrix dimension and the rank, up to logarithmic factors, whereas global guarantees for commonly used nonconvex methods require a higher polynomial dependence on the rank. We close this gap by analyzing Riemannian gradient descent (RGD) and Riemannian Gauss--Newton (RGN) methods. For an

n\times n

matrix of rank

r

with incoherence parameter

μ

and condition number

κ

, the two methods achieve exact recovery with high probability from

O(μnr\log n\log(nκ))

and

O(μnr\log n\log(2μrκ))

observations, respectively. The methods use a multiscale residual initialization, while the analysis simultaneously controls the spectral error and incoherence. The resulting RGD iterates converge linearly, whereas RGN eventually converges Q-quadratically.

Jian-Feng Cai, Xiliang Lu, Juntao You

Department of Mathematics, Hong Kong University of Science and Technology. · School of Mathematics and Statistics, Hubei Center for Applied Mathematics, and Hubei Key Laboratory of Computational Science, Wuhan University, Wuhan 430072, China. · School of Artificial Intelligence, Hubei Center for Applied Mathematics, and Hubei Key Laboratory of Computational Science, Wuhan University, Wuhan 430072, China.

Riemannian Optimization Nonconvex Optimization Matrix Completion

Ask PDF

Abstract

Nuclear Norm Minimization

Explore similar work

Guaranteed Low-Rank Tensor Recovery from Modewise Measurements via Normalized Block-Weighted Riemannian Gradient Descent

Sharp Restricted Isometry Thresholds for Global Minima of Rank-Restricted Matrix LASSO

Near-Optimal Nonconvex Matrix Completion