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

Guaranteed Low-Rank Tensor Recovery from Modewise Measurements via Normalized Block-Weighted Riemannian Gradient Descent
Sep 21, 2026Yushi Zhou, Feng ZhangRiemannian Optimization Tensor Decomposition
School of Mathematics and Statistics, Southwest University, Chongqing, China.
Sharp Restricted Isometry Thresholds for Global Minima of Rank-Restricted Matrix LASSO
Aug 29, 2026Richard Y. ZhangMatrix Optimization Sparse Recovery
Department of Electrical and Computer Engineering, University of Illinois Urbana–Champaign, Urbana, IL 61801 USA
Near-Optimal Nonconvex Matrix Completion
Sep 15, 2026Jian-Feng Cai, Xiliang Lu, Juntao YouRiemannian Optimization Nonconvex Optimization
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.

Sep 21, 2026J/K move · Enter open · S save

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

Yushi Zhou, Feng Zhang

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

Riemannian Optimization Tensor Decomposition

Open paper AskPDF arXiv

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.

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