Tight Majorizations and Convergence Rates of Nuclear Norm Minimization IRLS

• IRLS is motivated as a scalable alternative to nuclear norm solvers whose nonsmooth spectral structure can cause sublinear convergence and repeated full singular value decompositions.Nuclear norm minimization remains statistically mature and admits exact semidefinite programming formulations, but specialized computational methods face these scaling challenges.Source: §1 · p. 4
• The introduction identifies weight-operator choice as the central unresolved design issue because prior spectral IRLS work predominantly uses one-sided row- or column-space information.Existing convergence guarantees were limited mainly to convergence or subsequence statements, motivating the paper’s rate analysis.Source: §1 · pp. 4–5
• Harmonic-mean IRLS globally majorizes the smoothed nuclear norm through a new spectral comparison argument that handles noncommutativity.The proof uses a Sylvester-equation characterization and iterative pinching to establish the quadratic majorizer.Source: §1 · p. 5
• The harmonic mean is the tightest valid power-mean weight: global majorization holds precisely for q ≥ −1, with q = −1 producing the smallest quadratic model.Power means form a Loewner-ordered family of weight operators and corresponding quadratic models.Source: §1 · p. 6
• Under an order-r Schatten-1 null space property, IRLS achieves global linear convergence for admissible one-sided and power-mean weights from any positive-definite initialization.For approximately low-rank targets, the linear decay extends up to the best rank-r approximation error, while global contraction factors depend on dimension.Source: §1 · p. 6
• Harmonic-mean IRLS has a dimension-independent local linear rate near the ground truth, whereas one-sided methods can contract relative error by only order r/d.The one-sided lower bound holds for local instances satisfying the null space property, ruling out an analogous dimension-independent rate in general.Source: §1 · p. 6

Low-Rank Matrix Recovery

• Nonconvex rank-constrained methods use projections, factorizations, or Riemannian optimization, typically requiring the target rank and certified initialization for provable local convergence.Spectral initialization may be costly or noise-sensitive, and standard factorized gradient descent slows with increasing ground-truth condition number.Source: §2 · pp. 7–8
• Nuclear norm minimization is convex, rank-free, and admits global linear-rate algorithms independent of condition number, while this paper’s IRLS rates require neither prescribed step sizes nor restart schedules.The harmonic-mean MatrixIRLS local rate depends on the NSP constant η_r rather than directly on dimension.Source: §2 · p. 8

Low-Rank IRLS

• Foundational low-rank IRLS methods use one-sided reweighting and establish global convergence under NSP assumptions, but not convergence rates; later error-bound and stability results do not resolve this gap.The claimed local linear rate of Lai et al. (2013, p. 950) is described as unsubstantiated.Source: §2 · p. 8
• Kümmerle and Sigl (2018) proved local superlinear convergence for harmonic-mean IRLS in the Schatten-p case, but their theorem excludes the nuclear norm case p = 1.This paper adapts their Algorithm 1 to p = 1, while correcting a faulty proof that would have implied harmonic-mean majorization.Source: §2 · p. 9
• Recursive feature machines derive one-sided IRLS formulations and an SVD-free log-determinant implementation, but that implementation does not cover nuclear norm minimization and lacks rigorous low-rank IRLS convergence analysis.Related log-determinant IRLS work establishes local quadratic rates for geometric-mean weight operators under problem-specific assumptions.Source: §2 · p. 9

IRLS for Sparse Recovery

• Sparse IRLS has global and dimension-independent local linear rates, but separable vector objectives simplify weight design compared with spectral optimization, motivating tighter quadratic models for MatrixIRLS.Matrix weights have additional off-diagonal core entries with no sparse-recovery analogue.Source: §2 · pp. 9–10

3.1 IRLS for Low-Rank Recovery and Basic Properties

• MatrixIRLS smooths the nuclear norm, builds locally quadratic models from singular-value-based weight operators, and minimizes each model as a reweighted least-squares problem.The harmonic-mean version is the paper’s main algorithm; one-sided variants change only the weight-operator update.Source: §3.1 · pp. 10, 13

3.2 Majorization of Quadratic Model Implied by Harmonic-Mean Weights

• The harmonic-mean quadratic model globally majorizes the ε-smoothed nuclear norm, supplying the missing objective-progress property needed for convergence-rate analysis.The proof bounds the weighted inner product through a Sylvester equation and iterative pinching arguments, although the smoothing update still prevents a purely standard MM analysis.Source: §3.2 · pp. 14–15

3.3 Choice of the Smoothing Parameter

• Algorithm 1 updates ε using the scaled nuclear-norm tail β_er(X^(k))_*/d, coupling smoothing to the full spectrum rather than only σ_{er+1}(X^(k)).This rule is computationally attractive but is not covered by the global convergence-rate analysis when replaced by alternative updates; experiments suggest it succeeds over a wider sampling-factor range.Source: §3.3 · pp. 15–16

3.4 Optimality of Harmonic-Mean Weight Operator

• Left- and right-sided operators use only column- or row-space information, so transposing the problem can change their IRLS trajectories, whereas harmonic-mean weights avoid this pitfall and act on both spaces.The harmonic-mean operator also preserves symmetry in symmetric problems.Source: §3.4 · pp. 16–17
• Power-mean weight operators are Loewner-monotone in their parameter q, placing harmonic-mean weights at q = −1 within an ordered family that includes the one-sided variants.The ordering extends to the associated quadratic models and formalizes the family used to compare weight constructions.Source: §3.4 · p. 17
• The quadratic model majorizes the smoothed nuclear norm for every power-mean weight with q ≥ −1, including geometric and arithmetic means.Under the stated two-distinct-positive-singular-values condition, q ≥ −1 is necessary and sufficient.Source: §3.4 · pp. 17–18
• The harmonic mean is optimal within power-mean weights: any Loewner-smaller operator violates majorization locally.Thus it gives the pointwise smallest gap to the smoothed surrogate among majorizing power-mean variants.Source: §3.4 · p. 18
• This tightness is identified as the mechanism behind faster per-iteration progress and improved dimension-free local linear convergence for harmonic-mean MatrixIRLS.The paper contrasts this with larger-power-mean and one-sided variants, for which the improved local rate is not observed or is ruled out by a counterexample.Source: §3.4 · p. 18
• The harmonic-mean quadratic model is not a valid global majorizer for nonconvex Schatten-p minimization when 0 < p < 1.That nonconvex setting lies outside the paper’s scope, despite prior observations of improved local convergence for harmonic-mean reweighting.Source: §3.4 · p. 18

4.1 Preliminaries

• The NSP provides the recovery condition and a linear error bound needed for convergence analysis, but IRLS rates also require weight-operator-dependent control of quadratic forms.The NSP ensures unique nuclear-norm recovery and sharpness on the feasible set; unlike step-size methods, IRLS needs majorization and spectral bounds tied to the weight operator.Source: §4.1 · pp. 19–20

4.2.1 Rank-r Ground Truth X⋆

• Under the NSP, MatrixIRLS converges globally at a linear rate for exactly low-rank ground truths across harmonic, one-sided, and power-mean admissible weights.Theorem 3 assumes ηr < 3/5; the objective gap converges Q-linearly while the iterate distance converges R-linearly, with weight dependence entering through cq ∈ [1, 3].Source: §4.2 · p. 20, §4.2.1 · p. 21

4.2.2 Approximately Low-Rank Ground Truth

• For approximately low-rank ground truths, MatrixIRLS retains linear decay but converges to an approximation floor under the stronger condition ηr < 1/3.Theorem 4 applies to arbitrary X⋆ and gives global decay results whose constants satisfy 1.5 ≤ Aηr < 3.7 and 3.5 ≤ Bηr < 23/3 ≈ 7.67.Source: §4.2.2 · pp. 22–23

4.3 Fast Local Linear Rate of MatrixIRLS with Harmonic-Mean Weights

• Unlike the global rates, harmonic-mean MatrixIRLS has a dimension-independent local linear rate because its weighted quadratic form admits a sharp local upper bound.For ηr = 1/10, Theorem 5 gives cηr ≈ 0.0037, independent of d; with η1 = ηr, this local rate is faster than Theorem 3 when d > 273.Source: §4.3 · pp. 23–24
• A counterexample establishes a dimension-dependent lower bound for one-sided weight operators, whereas fast dimension-free local convergence is shown for harmonic and q-power means with q ∈ (−1, 0).For q ∈ [0, ∞], including arithmetic means, the result cannot be established from these results, and numerical experiments suggest the fast local linear rate should not be expected.Source: §4.3 · pp. 24–25

5.1 Setup

• Experiments use noiseless Gaussian rank-one matrix-sensing measurements, requiring m proportional to r(d1 + d2) for the convergence-theorem assumptions and reducing storage and evaluation costs.The setup uses O(m(d1 + d2)) entries and evaluates rank-r matrices in O(mr(d1 + d2)) operations instead of O(md1d2).Source: §5.1 · p. 26

5.2 Linear Convergence Rate Factors for IRLS with Weight Operator Variants

• Harmonic-mean IRLS is fastest across tested square dimensions: it reaches 10^-5 in at most 40 iterations for d ∈ {60, 90, 110, 140}, while alternatives exceed 300.For d = 30, harmonic, arithmetic, left-sided, and right-sided variants require 16, 49, 68, and 70 iterations, respectively.Source: §5.2 · pp. 26–27

5.3 Recovery of Rectangular Low-Rank Matrices

• In tall rectangular recovery, harmonic-mean IRLS remains fastest, reaching 10^-5 in 19, 28, and 38 iterations for d = 20, 40, and 80.The best alternative, right-sided IRLS, requires 40, 113, and 324 iterations, while left-sided IRLS fails within 500 iterations for d = 80.Source: §5.3 · pp. 29–30

5.4 Adversarial Initialization

• Adversarial initialization makes the first decrease factor grow approximately linearly with d, but harmonic-mean IRLS quickly recovers dimension-stable terminal behavior.Its terminal reciprocal contraction measure stays below 3.0 for d ∈ {100, 110, 120, 130, 140}, whereas other variants grow above 50 or nearly 40.Source: §5.4 · pp. 31–32

5.5 Role of the Smoothing Parameter Update Rules

• Across smoothing rules, ℓ∞-tail fails at oversampling C = 3 but converges at C = 4, while harmonic-mean IRLS remains faster than one-sided variants.At C = 4, ℓ∞-tail reaches the objective-gap threshold in 125 iterations and 2.29 seconds, compared with 43 iterations and 4.88 seconds for ℓ1-tail.Source: §5.5 · pp. 32, 34
• IRLS achieves order-of-magnitude speedups over generic SDP solvers: at C = 3.0 and 4.0, SCS takes 25.37 and 29.32 seconds, respectively.The ℓ1-tail rule remains the conservative, theoretically supported default because ℓ∞-tail is less robust at lower sampling levels.Source: §5.5 · pp. 34–35

6 Conclusion

• Harmonic-mean weights provide an arguably optimal IRLS design, supported by rigorous global majorization and tightness results.The conclusion frames the algorithm around weight operators and identifies the harmonic mean as the preferred choice within this analysis.Source: §6 · p. 35
• IRLS methods with multiple weight operators, including traditional and harmonic-mean variants, achieve global linear convergence from any initialization.Once iterates enter a neighborhood of the low-rank solution, the correct weight operator yields a dimension-free linear rate.Source: §6 · p. 35
• Experiments show substantially faster empirical linear convergence for harmonic-mean reweighting than one-sided or arithmetic-mean variants on rectangular and square instances.Adversarial initializations indicate that dimension dependence in the global rate is mainly transient during the algorithm’s initial phase.Source: §6 · p. 35
• The theory depends on a suitable null space property and leaves open dimension-free basin sizes, coverage of matrix completion, and tight majorizers for other spectral objectives.The conclusion also notes that ℓ2- and ℓ∞-tail continuation updates are not covered by the current convergence theory.Source: §6 · pp. 35–36

A Proofs of Main Results

• The convergence proofs are organized around Theorems 1–6, covering majorization, weight optimality, global rates, fast local rates, and impossibility for one-sided weights.The appendices separately establish the global majorization, optimality, global linear convergence, local linear convergence, and one-sided impossibility results.Source: A Proofs of Main Results · p. 36

A.1 Proof of Theorem 1 (Harmonic-Mean Quadratic Model Majorization)

• The harmonic-mean majorization proof reduces Theorem 1 to a lower bound on ⟨W_X,ε(Z), Z⟩_F, whose complicated weight-operator structure makes it harder than the one-sided case.For one-sided weights, the analogous lower bound follows directly from Cauchy–Schwarz.Source: §A.1 · pp. 36–37
• Lemma 2 supplies the needed harmonic-mean weighted-inner-product bound for arbitrary Z by using the singular-value structure of X and the regularized values λ_i = max(σ_i, ε).The proof then inserts this bound into the quadratic model and uses spectral variational arguments and the ε lower bound on the associated positive-semidefinite matrices.Source: §A.1 · pp. 37–38
• The majorization conclusion follows by splitting the scalar terms according to whether σ_k(Z) is at least ε, then summing the resulting bounds.This completes the proof that the harmonic-mean quadratic model globally majorizes the smoothed nuclear norm objective.Source: §A.1 · pp. 38–39

A.1.1 Proof of Lemma 2 via Iterative Pinching

• The harmonic-mean weight operator is the unique solution of a Sylvester equation involving both left and right positive-definite operators.The characterization follows from uniqueness of Sylvester-equation solutions and the singular-value-based definition of the operator.Source: §A.1.1 · p. 39
• Iterative pinching replaces the operators by simpler projected matrices until both are diagonal in the singular-vector bases of Z, enabling explicit solution and the desired lower bound.The construction uses projections onto singular-vector subspaces and repeats the majorization step until simultaneous diagonal structure is reached.Source: §A.1.1 · p. 40
• The abstract majorization lemma yields ⟨Z, W − f W⟩F ≥ 0 when the original and pinched Sylvester operators satisfy the stated projection, self-adjointness, and positive-definiteness conditions.The specialized Sylvester-equation lemma verifies these conditions using positive definiteness preserved by pinching.Source: §A.1.1 · pp. 41, 44, 45
• After d1 − 1 and d2 − 1 pinching iterations, the resulting left and right operators are diagonal in the chosen orthonormal bases.The recursive construction applies projection-based pinching operators to each matrix successively.Source: §A.1.1 · p. 46
• Iterative pinching preserves positive definiteness, diagonalizes the weight matrices in singular-vector bases, and yields the explicit Sylvester solution needed to prove Lemma 2.The argument applies pinching through rectangular cases and completes the lower bound on the weighted inner product.Source: §A.1.1 · pp. 46, 48, 49

A.2 Proof of Theorem 2 (Optimality of Harmonic Mean Quadratic Model)

• The proof establishes Theorem 2’s optimality result for the quadratic model induced by the harmonic-mean weight operator.The harmonic-mean operator is the model whose optimality is proved in this subsection.Source: §A.2 · p. 50

A.2.1 Proof of Lemma 1 (Monotonicity of Power Mean Weight Operators)

• For power-mean orders q ≤ q′, monotonicity gives Loewner ordering of the induced weight operators and domination of the corresponding quadratic models.The proof compares power means entrywise and derives quadratic-model domination from the Loewner ordering.Source: §A.2.1 · p. 50

Lemma 8

• Lemma 8 establishes differentiability, Lipschitz gradients, almost-everywhere second differentiability, and an explicit Hessian formula for spectral functions.The result applies when f′ is Lipschitz, right differentiable at zero, and satisfies f′(0) = 0; twice differentiability of the spectral function is characterized by that of f at the singular values.Source: §A.2.2 · p. 51

Lemma 9

• The proof of Lemma 9 reduces perturbations of X to a two-dimensional singular block, so the smoothed objective difference depends only on singular values σ_i and σ_j.Orthogonal changes of basis make X + tZ block diagonal, yielding Jε(X + tZ) − Jε(X) = F2(B + tN) − F2(B), while all other singular-value terms cancel.Source: §A.2.2 · pp. 52–53
• Local majorization forces the second derivative of the perturbation gap to be nonpositive, yielding the stated necessary condition for every pair σ_i, σ_j > ε without assumptions on the remaining singular values.The argument does not require Jε to be twice differentiable at the full matrix X; local maximality along the selected perturbation suffices.Source: §A.2.2 · pp. 52, 54
• Applying Lemma 8 to the 2 × 2 block shows that the perturbation gap has zero first derivative and a computable second derivative at zero.For σ_i > ε and σ_j > ε, the relevant spectral function is twice differentiable; the skew-symmetric perturbation eliminates the first-order term and activates the Hessian contribution.Source: §A.2.2 · pp. 53–54

A.2.3 Proof of Theorem 2

• For every q ≥ −1, the power-mean quadratic weight operator majorizes the smoothed nuclear norm globally.This follows from harmonic-mean majorization and monotonicity of power-mean weight operators.Source: §A.2.3 · p. 54
• When q < −1, choose two distinct singular values σ_i, σ_j > ε to construct a violation of the majorization condition.Their distinctness implies distinct reciprocal-smoothed values, enabling strict power-mean monotonicity.Source: §A.2.3 · p. 54
• For q < −1, strict power-mean monotonicity makes the necessary condition for majorization fail for the index pair (i, j).The argument uses symmetry of the power-mean core matrices and contraposition of Lemma 9.Source: §A.2.3 · pp. 54–55
• Consequently, ε(· | X) does not majorize Jε locally around X: for every δ > 0, there exists Δ ∈ R^(d1×d2) with ||Δ||F ≤ δ violating majorization.Source: §A.2.3 · p. 55
• Therefore, global majorization also fails for every q < −1, completing the proof of harmonic-mean optimality.The contradiction is established through local failure, which rules out global majorization.Source: §A.2.3 · p. 55

A.3.1 Preliminaries and General Proof Strategy

• Under the NSP, Lemma 11 compares the smoothed nuclear norm J_ε(X) with the nuclear norm error when A(X⋆)=A(X) and ε≤β_r(X)∗.The proof uses J_ε(X)≥∥X∥∗, the NSP reverse inequality, and a separate argument for ε>0; ε=0 follows by convention.Source: §A.3.1 · pp. 55–56
• The convergence proofs track J_εk(X(k))−∥X⋆∥∗ through a quadratic-model descent inequality, optimizing an auxiliary scalar t after bounding its two terms.The same estimate controls term (a) globally and locally, whereas proximity to X⋆ enables sharper bounds for term (b) with harmonic-mean weights.Source: §A.3.1 · pp. 56–57
• The strategy applies when the quadratic model majorizes the smoothed nuclear norm for harmonic, power-mean, and established one-sided weight operators.This connects the majorization property to the global and local linear convergence analyses developed in the appendix.Source: §A.3.1 · p. 57

A.3.2 Upper Bounds on Quadratic Forms Implied by Weight Operators

• Hadamard-product norm bounds for the weight core matrix are used to upper-bound ⟨X⋆−X, W_X,ε(X⋆−X)⟩_F, controlling quadratic term (b).Lemmas 13–15 provide the auxiliary bounds, with the weight core representing the non-isometric part of the weight operator.Source: §A.3.2 · pp. 58, 59, 63
• For power-mean core matrices, the Hadamard-product bound is λmax|||B||| for q∈[−∞,1] and 3λmax|||B||| for q∈(1,∞].The first regime includes harmonic and arithmetic means as special cases through the power-mean framework.Source: §A.3.2 · pp. 59, 62
• The harmonic-mean case is handled through positive semidefiniteness: the matrix with entries 1/(λ_i+λ_j) is positive semidefinite.This permits direct application of the positive-semidefinite Hadamard-product inequality to obtain the required norm bound.Source: §A.3.2 · p. 60
• Under the order-r and order-one NSPs, the resulting quadratic bounds cover harmonic, one-sided, and power-mean weights, yielding constant 1 for q≤1 and c_q≤3 for q>1.The harmonic case q=−1 is included in the q≤1 regime; for q>1, the proof uses 1<c_q≤3.Source: §A.3.2 · pp. 63–64

Proof of Theorem 3

• Proposition 2 quantifies objective decrease for admissible weight operators, assuming positive-definite initialization, rank estimate r, and ε_k > 0.Its descent argument combines quadratic majorization with the optimality of the next IRLS iterate.Source: §A.3.3 · pp. 64–65
• The decrease bound is obtained by minimizing the quadratic model along the error direction N^(k) = X⋆ − X^(k), using estimates from Lemmas 12 and 16.The proof selects a nonnegative line-search parameter t to make the quadratic-model difference negative.Source: §A.3.3 · p. 65
• The weight-dependent constant c_q equals 1 for one-sided, harmonic-mean, and power-mean weights with q ∈ [−1,1], while 1 < c_q ≤ 3 for q ∈ (1,∞].Thus the proposition’s convergence constants distinguish the weight families through c_q.Source: §A.3.3 · p. 66
• Under the NSP of order r with η_r < 3/5, IRLS converges globally at a linear rate when X⋆ is exactly rank r.The proof chains Proposition 2 over all preceding iterations and derives the stated convergence bound from the NSP condition.Source: §A.3.3 · p. 66
• The proof of the second convergence inequality combines the established rate with Lemma 11 and the Eckart–Young theorem.These steps provide the auxiliary low-rank approximation bound needed to complete Theorem 3.Source: §A.3.3 · pp. 66–67

Proof of Theorem 4

• The argument proves global linear convergence by chaining a one-step estimate up to the threshold iteration ˆk and extending it afterward using monotonicity of J_εk(X^(k)).When β_r(X⋆)* = 0, ˆk = ∞ and Proposition 2 applies throughout; otherwise, the post-threshold bound follows from the estimate at ˆk.Source: §A.3.4 · pp. 67–68
• The proof derives inequality (33) by combining the established convergence estimate with Lemma 11, the Eckart–Young theorem, and a triangle-inequality bound involving the best rank-r approximation X⋆,r.The resulting constant is expressed using A_ηr and the factor involving η_r from the theorem statement.Source: §A.3.4 · p. 68
• Under η_r < 1/3, the proof establishes inequality (34) for iterations k ≥ ˆk by combining monotonicity, Lemma 11, approximation estimates, and the definition of ˆk.The condition η_r < 1/3 is used in the final inequality leading to the stated bound.Source: §A.3.4 · pp. 68–69
• At k = ˆk − 1, inequality (33) is combined with another inequality; ηr < 1/3 implies Bηr < 23/3 < 9, making the left-hand side positive.Taking logarithms and using −log(1 − x) ≥ x for x ∈ (0, 1) completes the claimed argument.Source: §A.3.4 · p. 69

A.4 Proofs of Theorems 5 and 6 (Local Linear Convergence and Counterexample)

• The refined local estimate removes ε-dependence from the quadratic mismatch bound and improves the convergence rate by a factor of d over the global analysis.This sharper estimate underpins Theorem 5 for harmonic-mean and related q-power mean operators.Source: §A.4 · p. 69, §A.4.1 · p. 70
• One-sided weight operators cannot generally achieve the same dimension-independent local rate, even in arbitrarily small neighborhoods of X⋆.The counterexample covers left-sided and right-sided core-matrix constructions and establishes Theorem 6.Source: §A.4 · p. 69

A.4.1 Tight Upper Bounds on Harmonic-Mean Quadratic Forms

• The technical bound applies to q-power mean weights with q ∈ [−1, 0), when the iterate is sufficiently close to the rank-r ground truth X⋆.The harmonic-mean operator is the special case q = −1.Source: §A.4.1 · p. 70
• Under an order-r NSP with ηr ≤ 3/5 and exact measurements A(X) = A(X⋆), Lemma 17 provides the required upper bound on the harmonic-mean quadratic form.The estimate is expressed in terms of the nuclear-norm error and the smoothing parameter condition, with the ε-dependence eliminated in the resulting local bound.Source: §A.4.1 · p. 70
• For q = −1, the bound is approximately 27.20 ∥X − X⋆∥∗ when ηr = 1/10 and 298 ∥X − X⋆∥∗ when ηr = 1/2.These examples quantify the dependence of the bound on the NSP constant.Source: §A.4.1 · p. 70
• The proof combines power-mean inequalities with an order-one NSP norm bound, Weyl’s inequality, singular-value approximation, and Wedin’s sin θ theorem.The argument decomposes the quadratic form into support-related summands and controls them using these ingredients.Source: §A.4.1 · pp. 70, 71, 72, 74
• Lemma 19 supplies an explicit lower bound for the smoothing parameters εk, verifying the condition needed by Lemma 17 along MatrixIRLS iterates.It covers q-power mean operators with q ∈ [−1, ∞] and one-sided weight operators under an order-r NSP.Source: §A.4.1 · p. 75

One-Step Local Contraction

• Proposition 4 establishes one-step local contraction for q-power mean weight operators with q ∈ [−1, 0), assuming a measurement operator satisfies the NSP of order r.The setup uses rank estimate r and requires εk > 0 so that X(k+1) is defined.Source: §A.4.2 · p. 76
• For harmonic-mean weights, q = −1 yields the displayed specialized contraction factor and completes the proof of Proposition 4.The harmonic specialization uses 2^(-1/q) = 2 in the general contraction expression.Source: §A.4.2 · pp. 77–78

Proof of Theorem 5

• Theorem 5 establishes dimension-independent local linear convergence for MatrixIRLS with harmonic-mean weight operators.The proof uses Proposition 4 with q = −1 and verifies the contraction recursively.Source: §A.4.2 · pp. 78–79
• The induction proves both convergence and auxiliary iterate conditions at every subsequent iteration, completing the theorem once the base case is established.The induction step combines the proposition with the null space property, the induction hypothesis, Lemma 11, and the Eckart–Young theorem.Source: §A.4.2 · p. 79

A.4.3 Proof of Theorem 6 (Counterexample for One-Sided IRLS)

• One-sided IRLS can reduce nuclear norm error by at most a factor of 1 − cr/d in an explicit counterexample.The construction applies to left-sided weights and extends to right-sided weights by transposition.Source: §A.4.3 · p. 80
• The explicit construction sets d ≥ 220r and uses a rank-structured perturbation whose singular values support the counterexample’s null-space and error calculations.The perturbation has r + h = 11r repeated singular values with h = 10r.Source: §A.4.3 · p. 80
• The counterexample uses a measurement operator satisfying the Schatten-1 null space property while producing a large one-sided quadratic-form lower bound.Specifically, the construction gives ⟨X − X⋆, W_X,ε(X − X⋆)⟩F ≥ d/(220r) ∥X − X⋆∥∗.Source: §A.4.3 · p. 81
• For the weighted least-squares step, the feasible set is an affine line, and its minimizer establishes the stated lower bound on the next IRLS iterate’s error.This completes the one-step argument underlying the factor limitation.Source: §A.4.3 · pp. 81–82

B Complementary Proofs

• The appendix explains that the complementary proofs establish known IRLS-model facts, identify an incorrect literature proof, and analyze one-sided majorization arguments.These results include proofs for Proposition 1, Lipschitz continuity, and one-sided quadratic majorization.Source: B Complementary Proofs · p. 82

B.1 Proof of Proposition 1 (Properties of the IRLS Quadratic Model)

• Proposition 1 follows for one-sided, harmonic-mean, and q-mean weights because the core diagonal entries equal max(σ_i, ε)^−1 and the weight operator is self-adjoint.The self-adjoint Hadamard representation yields the simplified quadratic model, with Q_ε(X | X) = J_ε(X).Source: §B.1 · pp. 82–84

B.2 Lipschitz Gradients of Smoothed Nuclear Norm

• The smoothed nuclear norm J_ε is differentiable, and its gradient is a non-Hermitian Loewner operator whose Lipschitz continuity follows from singular-value calculus.The scalar map g_ε(σ) = σ max(σ, ε) has Lipschitz constant 1/ε, yielding the corresponding Frobenius-norm gradient bound.Source: §B.2 · p. 84

Prior majorization result

• One-sided quadratic models globally majorize the ε-smoothed nuclear norm, supporting the IRLS methods of Fornasier et al. (2011) and Mohan and Fazel (2012).This is the stated global majorization proposition for left-sided and right-sided weight operators.Source: §B.3 · p. 84

Proof strategy

• For one-sided weights, the majorization inequality can be proved variationally through an auxiliary functional, consistent with proofs for separable ℓ1-type objectives.The cited related literature includes Geman and Reynolds (1992), Charbonnier et al. (1997), Daubechies et al. (2010), and Ochs et al. (2015).Source: §B.3 · p. 84

Proof limitations

• The section presents three proofs for one-sided-weight majorization and explains why these strategies do not extend to harmonic-mean weights.The proofs appear in Appendices B.3.1–B.3.3, while the limitation is discussed in Appendix B.3.4.Source: §B.3 · pp. 84–85

B.3.1 Proof of Proposition 5 Using Concavity Arguments

• Concavity of a transformed matrix functional establishes the majorization property (96) for one-sided weight operators with core matrices (4) or (5).The argument uses concavity of Jε after a change of variables and the induced spectral trace function Gε.Source: §B.3.1 · pp. 85–86
• The concavity proof linearizes Gε(ZZ⊤) at XX⊤ and uses the gradient condition to obtain the required quadratic upper bound.The proof identifies the weight action with left matrix multiplication for the one-sided operator.Source: §B.3.1 · pp. 85–86
• This change-of-variables concavity strategy remains elusive for harmonic-mean weights because their operators are not simple left- or right-matrix multiplications.The limitation is specific to extending the presented proof strategy beyond one-sided operators.Source: §B.3.1 · p. 86

B.3.2 Proof of Proposition 5 Using Variational Calculus

• Variational calculus derives the one-sided majorization property from the auxiliary formulation underlying IRLS-M, with the right-sided case obtained by transposition.The auxiliary variable is minimized over a restricted positive-definite domain, producing the smoothed nuclear-norm surrogate up to a dimension-dependent constant.Source: §B.3.2 · pp. 86–87
• The auxiliary minimizer has diagonal entries 1/max(σi(Z), ε), matching the left-sided weight operator and yielding equality in the scalar lower bounds.The minimizer uses the unconstrained critical point when σi(Z) ≥ ε and the boundary value when σi(Z) < ε.Source: §B.3.2 · p. 87
• Freezing the auxiliary variable at the base point X and cancelling the dimension-dependent constant proves (96) for left-sided weights, with right-sided weights following analogously.The right-sided derivation replaces ZZ⊤ with Z⊤Z.Source: §B.3.2 · pp. 87–88

B.3.3 Proof of Proposition 5 Based on Appendix A.1

• The Appendix A.1-based proof reuses the quadratic-model representation and isolates the one-sided case’s only new ingredient as a lower bound for ⟨WX,ε(Z), Z⟩F.The remaining spectral and scalar estimates follow the preceding harmonic-proof pattern, with the proof for right-sided weights obtained by transposition.Source: §B.3.3 · p. 88

Variational strategy

• Kümmerle and Sigl (2018) propose an auxiliary-variable variational formulation whose formal minimizer would yield harmonic-mean weights and a quadratic majorizer.Freezing the auxiliary variable at the proposed minimizer could explain the update through alternating minimization, but the needed variational characterization is incomplete.Source: §B.3.4 · p. 89

Structural obstacle

• The harmonic-mean operator couples left and right singular spaces through an inverse Kronecker sum, so auxiliary minimization does not decouple into scalar problems after one basis change.This contrasts with the one-sided functional used in Appendix B.3.2.Source: §B.3.4 · p. 89

Proof gaps

• Kümmerle and Sigl (2018) differentiate matrix square roots as if scalar chain rules applied, although noncommuting perturbations require Fréchet derivatives involving divided differences or Sylvester operators.Consequently, their stationarity equation is not justified by the cited matrix-calculus rules.Source: §B.3.4 · pp. 89–90
• Their subsequent commutation arguments do not establish that the auxiliary variable’s singular vectors align with those of Z, leaving the claimed global minimizer Mopt unproved.The stated implications require additional nondegeneracy assumptions and stronger conclusions than the displayed relations provide.Source: §B.3.4 · p. 90

Resolution and scope

• The paper therefore proves the p = 1 majorization result using a direct lower bound for ⟨W_X,ε(Z), Z⟩F, while leaving nonconvex 0 < p < 1 surrogates for future work.The authors regard Kümmerle and Sigl (2018, Lemma 14) as correct for p = 1 but likely incorrect for 0 < p < 1.Source: §B.3.4 · p. 90