Approximating Matrix p-norms

1 Introduction

• The norm generalizes largest-singular-value computation at p = q = 2 and includes the Grothendieck problem at p = 1, q = ∞.The paper emphasizes that different parameter ranges have substantially different algorithmic flavors.Source: §1 · p. 2

1.1 Our Results

• For non-negative matrices with 1 ≤ p ≤ q, the paper gives a polynomial-time (1 + δ)-approximation algorithm.The algorithm is based on a fixed-point iteration analogous to power iteration.Source: §1.1 · p. 3
• The fixed-point analysis also yields an O(log n)-competitive oblivious routing scheme for every ℓp norm with p ≥ 1.Matrix p-norm computation serves as a separation oracle within a multiplicative-weights-style update, extending the constructive result beyond p = 2.Source: §1.1 · p. 3
• For unrestricted matrices, approximating the q->p norm within any constant factor is NP-hard when q ≥ p > 2 and, by duality, when p ≤ q < 2.Under NP not in quasi-polynomial time, approximation within Ω(2^(log n)^(1−ε)) is also hard for these ranges.Source: §1.1 · p. 3
• The paper’s techniques use Max-Cut gadget reductions, tensoring for p->p norms, and a conversion from hard p->p instances to q->p instances when q > p > 2.The q->p norms generally do not multiply under tensoring, motivating the conversion step.Source: §1.1 · p. 4

1.2 Related work.

• The paper situates its results among prior approximation algorithms, hardness results, and related Lp Grothendieck formulations summarized in comparison tables.The tables compare general algorithms, non-negative-matrix algorithms, and hardness across parameter ranges.Source: §1.1 · p. 4, §1.2 · pp. 4–5, Table 1 · p. 5

1.1 Our Results

• The paper leaves the p > q regime unresolved, including for non-negative matrices, and notes possible connections to dense-subgraph and hypercontractive-norm problems.For p > q, the authors do not know corresponding algorithmic or hardness results, even though multiple optima may occur.Source: §1.1 · p. 4

2 Notation and Simplifications

• The notation sets A_i for the ith row, a_ij for matrix entries, x_i for vector coordinates, and x ∝ y for positive proportionality.A vector is called positive when all coordinates are greater than zero.Source: §2 · p. 6
• For algorithmic results, matrices are restricted to entries in [1/N, 1], because zero entries can cause minor problems.After scaling the largest entry to one, the paper adds (1/N)J with N approximately (m + n)^2/δ to obtain the required positive matrix.Source: §2 · p. 6

3.1 Algorithm description

• The algorithm rewrites ∇f = 0 as a fixed-point equation Sx = x, starts from a vector, and repeatedly applies S; for p = 2, this mimics power iteration, with S equal to multiplication by A up to normalization.Source: §3 · p. 6
• Every positive fixed point is a critical point, and there is a unique positive fixed point that is also the unique maximum of f.The unique maximizer is therefore the unique fixed point of the iteration.Source: §3.1 · p. 7, §3.2 · p. 7

3.2 Analyzing the Algorithm

• The proof shows that a maximizer lies in the positive orthant and is an interior fixed point, while the objective is nondecreasing along the iteration.These properties support the fixed-point characterization and convergence argument.Source: §3.2 · p. 7
• The analysis tracks potentials m(x) and M(x): each iteration increases m(x), decreases M(x), and significantly narrows their ratio when it is large.At a fixed point, the two potentials coincide and characterize the norm value.Source: §3.2 · pp. 7–8
• After T = (Nn)polylog(N, n, 1/δ) iterations, the algorithm finds x with f(x) ≥ (1 −δ)f(x∗), giving a polynomial-time approximation to ∥A∥q→p.The convergence analysis starts from matrices whose entries lie in [1/N, 1].Source: §3.2 · p. 9

4 Proximity to the optimum

• Combining local concavity with connected level sets shows that if f(x) is close to f(x∗), then x − x∗ is small.The paper notes that the formal proximity proof is given for p = q, the case used in the routing application.Source: §4 · pp. 9, 12
• The objective is not concave everywhere; the concavity guarantee is restricted to neighborhoods of critical points.The paper explicitly notes this limitation in a footnote.Source: §4 · pp. 9–10
• The function f is strictly concave around every critical point, so its Hessian is negative semidefinite there.This provides local control of objective changes around the optimum.Source: §4 · p. 10
• Every upper level set Nτ is connected, preventing separate high-value regions away from the unique global optimum.The proof uses uniqueness of the critical point and the geometry of the normalized domain.Source: §4 · p. 11
• The computed vector is within ℓ1 distance 1/(Nn)^c of x∗ after polynomially many iterations, enabling computation of x∗ to any accuracy.The bound follows by showing the negative Hessian term dominates higher-order terms.Source: §4 · p. 13

5 An Application - O(log n) Oblivious routing scheme for ℓp

• Englert and Räcke established existence of O(log n)-competitive schemes for all ℓp norms but efficiently constructed them only for p = 2.Their constructive proof relied on orthonormal eigenspaces.Source: §5 · pp. 13–14
• Unique optima and stability make matrix p-norm computation usable as a separation oracle in multiplicative-weights updates, yielding an O(log n)-competitive scheme for all ℓp norms with p ≥ 1.This extends the constructive scope of beyond p = 2.Source: §5 · p. 13
• The routing problem reduces the competitive ratio of a tree-based scheme to a matrix p-norm, represented as max∥u∥p≤1∥Mu∥p.A zero-sum game over routing matrices and positive unit p-norm vectors captures the worst-case demand.Source: §5 · pp. 13–14
• Theorem 5.4 gives a polynomial-time algorithm for an oblivious routing scheme with competitive ratio O(log n) for ℓp aggregation and norm-valued edge loads.The result applies when p > 1.Source: §5 · p. 15
• The algorithm iteratively improves a tree-based routing matrix by finding a violating vector through the matrix-norm procedure and updating the scheme.Each iteration decreases the matrix p-norm by Ω(1/poly(n)), so polynomially many steps suffice.Source: §5 · p. 15

6.1 Inapproximability of ∥A∥p7→p

• For p ≥ 2, approximating the matrix p→p norm is NP-hard within a fixed constant factor via a reduction from gap MaxCut.The reduction uses a graph-based objective whose good assignments encode cut edges; for p > 2, a technical lemma separates good, same-sign, and bad variable pairs.Source: §6.1 · pp. 16, 18

6.2 Amplifying the gap by tensoring

• For square matrices and p ≥ 1, tensoring preserves the p-norm multiplicatively, while approximating matrix p-norms within any factor γ is NP-hard under the stated assumption.Source: §6.2 · pp. 19–20

6.3 Approximating ∥A∥q7→p when p̸ = q.

• For q ≥ p > 2, approximating the q→p norm is NP-hard within any fixed constant γ.Because direct tensoring does not preserve q→p norms when q ≠ p, the proof transforms the structured p-norm hardness instance using a differently scaled coordinate and norm inequalities.Source: §6.3 · pp. 21–22
• The q→p hardness construction for q ≠ p is obtained by transforming the p-norm instance rather than tensoring a q→p instance.The transformed instance retains a ±1 completeness assignment and uses the structured thresholds from Claim 6.7 to obtain an arbitrarily large constant gap.Source: §6.3 · pp. 21–22

6.4 Approximating ∥A∥∞7→p

• Computing the ∞→p norm is equivalent to finding the longest vector formed by a linear combination of the matrix’s column vectors.This identifies the norm with the Longest Vector problem for the columns v_i of A.Source: §6.4 · pp. 22–23

6.4 Approximating ∥A∥∞→p

• Computing ∥A∥∞→p is equivalent to finding the longest vector among the column vectors of A.The maximization is attained when every coordinate satisfies |x_i| = 1.Source: §6.4 · p. 23
• The ∞→p norm extends Grothendieck-type problems: p = 1 gives the original problem, p = 2 gives the ℓ2 version, and 1 ≤ p ≤ 2 has a constant-factor approximation.For p > 2, the theorem supplies the corresponding quasipolynomial-time hardness guarantee.Source: §6.4 · p. 23
• It is NP-hard to approximate ∥A∥∞→p within any constant γ for p > 2, and hard within Ω(2(log n)1−ε) for constant ε > 0 unless NP ∈ DTIME(2polylog(n)).The hardness follows from the techniques of Theorem 6.8, which also apply when q = ∞.Source: §6.4 · p. 23

• The matrix p-norm objective is generally not a convex optimization problem because maximizing ∥Ax∥p is not equivalent to efficiently minimizing a convex function.The section notes that the optimization is not generally convex and contrasts it with convex minimization over convex domains.Source: §A.1 · p. 25
• For p=2.5, f((x + y)/2) < (f(x) + f(y))/2, so f is not concave.The midpoint inequality provides a concrete witness to non-concavity.Source: §A.1 · p. 25
• The possibility that a power of f might be concave remains open in this discussion.Source: §A.1 · p. 25

• The identity ∥u∥p = max_{y: ∥y∥p′=1} yT x provides a dual-norm representation used to move between parameter ranges.The passage states that p′ is the dual norm exponent and similarly defines q′.Source: §A.2 · p. 25
• The dual exponent p′ satisfies 1/p + 1/p′ = 1, and q′ is defined analogously for q.Source: §A.2 · p. 25

• Adding a very small positive number to every matrix entry leaves the q→p norm nearly unchanged.This is the stated purpose of the perturbation argument.Source: §A.3 · p. 25
• Lemma A.1 normalizes the maximum entry of A to 1 and compares it with Jε, the matrix whose entries are all ε.Source: §A.3 · p. 25
• Because the normalized matrix has q→p norm at least 1, the perturbation can be controlled relative to the original norm.The proof begins by observing ∥A∥q→p ≥ 1 when the maximum entry is 1.Source: §A.3 · p. 25
• The all-ε matrix is maximized by an equal-entry vector, yielding a bound on its q→p norm.Source: §A.3 · p. 25
• The lemma follows by applying the triangle inequality because the q→p quantity is a norm in the matrix argument.Source: §A.3 · p. 25