PaperlayerView exact revision on arXiv

Source-linked AI summary

Perron-Frobenius Theory in Nearly Linear Time: Positive Eigenvectors, M-matrices, Graph Kernels, and Other Applications

AmirMahdi Ahmadinejad, Arun Jambulapati, Amin Saberi, Aaron Sidford

arXiv:1810.02348v1cs.DSmath.OC

TL;DR

Earlier Perron-vector algorithms were quadratic, restricted to special cases, or depended too strongly on accuracy and conditioning. The paper uses a shift-and-invert-related reduction to RCDD systems to obtain nearly linear-time algorithms, including Perron-vector computation and M-matrix solving.

  • Problem

    Previously known Perron-vector algorithms were quadratic, restricted to special cases, or depended more than polylogarithmically on accuracy or relevant condition numbers.

    Source: §1 · p. 2

  • Method

    The paper reduces M-matrix solving to RCDD systems using a new method related to shift-and-invert preconditioning.

    Source: §1 · p. 3, §1.3 · p. 6

  • Results

    The paper gives nearly linear-time algorithms for Perron vectors and M-matrix systems; for non-negative irreducible A, Perron estimation runs in ˜O(m) time and returns s with (1−δ)ρ(A)<s≤ρ(A).

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    The method also improves running times for canonical random-walk graph kernels.

    Source: §6.4 · p. 34

    The iterative strategy needs an upper bound on a convergence-iteration function, but its dependence on the left and right Perron-vector condition numbers is unknown in advance.

    Source: §3.3.1 · p. 15

Abstract

from arXiv · show

In this paper we provide nearly linear time algorithms for several problems closely associated with the classic Perron-Frobenius theorem, including computing Perron vectors, i.e. entrywise non-negative eigenvectors of non-negative matrices, and solving linear systems in asymmetric M-matrices, a generalization of Laplacian systems. The running times of our algorithms depend nearly linearly on the input size and polylogarithmically on the desired accuracy and problem condition number. Leveraging these results we also provide improved running times for a broader range of problems including computing random walk-based graph kernels, computing Katz centrality, and more. The running times of our algorithms improve upon previously known results which either depended polynomially on the condition number of the problem, required quadratic time, or only applied to special cases. We obtain these results by providing new iterative methods for reducing these problems to solving linear systems in Row-Column Diagonally Dominant (RCDD) matrices. Our methods are related to the classic shift-and-invert preconditioning technique for eigenvector computation and constitute the first alternative to the result in Cohen et al. (2016) for reducing stationary distribution computation and solving directed Laplacian systems to solving RCDD systems.

1 Introduction

The paper addresses limitations in algorithms for Perron vectors and M-matrix systems with nearly linear-time methods, reducing these problems to RCDD linear systems. It also connects the two problem families and applies the results to additional matrix and graph problems.

1.2 Previous Work

  • Earlier Perron-vector algorithms were quadratic, limited to special cases, or more than polylogarithmic in accuracy or relevant condition numbers.Generic sparse linear-system methods could also take quadratic time, while prior M-matrix results had narrower scope or conditioning dependence.Source: §1 · p. 2, §1.2 · p. 5

1.4 Overview of Results

  • For a non-negative irreducible matrix A, the Perron algorithm runs in ˜O(m) time and returns s with (1−δ)ρ(A)<s≤ρ(A), plus positive left and right Perron vectors.The guarantee depends on K=Θ(κ(v_l)+κ(v_r)).Source: §1 · p. 2
  • For M=sI−A with ρ(A)<s, an ˜O(m)-time algorithm computes an operator P with expected relative residual at most ǫ for every vector b.The bound assumes K≥max{s∥M−1∥∞,s∥M−1∥1}.Source: §1 · p. 3

1.1 M-Matrices, Positive Matrix Sums, and Perron Vectors

  • Perron-vector computation and M-matrix solving are interdependent: each can support the other, creating a circularity the paper's method is designed to break.The paper identifies a variant of shift-and-invert preconditioning as its way to escape this dependency.Source: §1.1 · pp. 4–5

1.3 Overview of Approach

  • The approach reduces M-matrix solving to RCDD systems using a shift-and-invert-related method and a sequence of increasingly less regularized systems.The algorithm starts with a large α and successively uses a solver for M_α to solve M_{α/2}.Source: §1.3 · p. 6

1.4 Overview of Results

  • The results also cover Leontief-model checks, Katz centrality, top singular vectors of non-negative matrices, and improved running times for random-walk graph kernels.The singular-vector application requires additional ingredients for solving RCDD systems.Source: §1.4 · p. 7

2 Preliminaries

The preliminaries establish notation and matrix classes used throughout the paper, then state the Perron–Frobenius properties and RCDD framework that support the later algorithms.

2.1 Notation

  • Matrix and vector conventions, matrix ordering, norms, and spectral quantities provide the notation used throughout the paper.Source: §2.1 · p. 8

2.2 M-Matrices

  • An M-matrix has the form M = sI − B, where s > 0, B is entrywise nonnegative, and ρ(B) ≤ s.The paper introduces basic M-matrix facts needed for its analysis.Source: §2.2 · p. 9

2.3 Perron-Frobenius Theorem

  • The Perron–Frobenius properties include a simple positive eigenvalue with positive left and right eigenvectors, and a Collatz–Wielandt characterization of that eigenvalue.Source: §2.3 · p. 9

2.4 Row Column Diagonally Dominant Matrices

  • The paper reduces M-matrix systems to RCDD systems, where diagonal entries dominate the off-diagonal sums in both rows and columns.Source: §2.4 · p. 9
  • Algorithms use an RCDD solver as a black-box oracle and parameterize their running times by its cost, with nearly linear RCDD solvers available [3] [4].Source: §2.4 · pp. 9–10

3 A Technical Overview of Approach

The overview connects M-matrices to RCDD systems through positive diagonal scaling, then uses iterative solving and an M-matrix decision procedure to approach the Perron problem.

3.1 From M-Matrices to RCDD Matrices

  • Positive diagonal scalings make an M-matrix RCDD, linking its linear systems to nearly linear-time RCDD solving.Conversely, positive scalings that make sI − A RCDD certify that it is an M-matrix.Source: §3.1 · p. 11

3.2 Algorithm for Solving Linear Systems in M-matrices

  • The algorithm solves M-matrix systems by repeatedly scaling shifted matrices and using a nearby shift as a preconditioner.The overview says the full analysis handles approximate operations with at most polylogarithmic overhead.Source: §3.2 · pp. 11, 13

3.3 Finding the top eigenvalue and eigenvectors of positive matrices

  • The overview frames computing a Perron vector as finding the top eigenvalue and eigenvectors of a non-negative matrix.It also presents the problem as equivalent to deciding whether sI − A is an M-matrix.Source: §3.3 · p. 14

3.3.1 The M-matrix Decision Problem

  • The M-matrix decision procedure uses bounded Richardson iterations to distinguish failure from successful scaling of a shifted matrix.Success yields a certificate that Mε is an M-matrix; failure within the iteration bound certifies that M is not an M-matrix.Source: §3.3.1 · p. 14
  • The decision strategy requires an iteration bound tied to the condition numbers of the left and right eigenvectors, which are not known in advance.The overview points to a doubling scheme to handle this unknown bound.Source: §3.3.1 · p. 15

3.3.2 Perron problem

  • Binary search with the M-matrix decision procedure estimates ρ(A), then a shifted linear solve yields approximate eigenvectors.The overview states that the resulting vector is a 2ε-approximate eigenvector in infinity norm when using ρ(A).Source: §3.3.2 · p. 15

4 Numerically Stable M-Matrix Scaling

This section develops a numerically stable scaling procedure for M-matrices, using RCDD solves and iterative preconditioning to compute the needed scalings and operators.

Numerically Stable M-Matrix Scaling

  • The method advances from scalings of one shifted matrix to a nearby shift by preconditioning with an operator built from RCDD solves.It applies iterative solving to obtain the left and right scaling vectors for the new shift.Source: §4 · p. 16

M-Matrix Scaling

  • ˜O(m) time suffices to compute positive diagonal scalings L and R making ((1 + ε)sI − A) RCDD, given K ≥ max(s∥M⁻¹∥∞, s∥M⁻¹∥₁).The theorem gives high-probability success for nonnegative A with m nonzero entries and ρ(A) < s.Source: §4 · p. 21

Solving M-matrix Systems

  • The resulting operator P solves M systems with expected residual ∥b − MP(b)∥₂ ≤ ε∥b∥₂ in ˜O(m) time.The guarantee applies for K ≥ max{s∥M⁻¹∥∞, s∥M⁻¹∥₁} and ρ(A) < s.Source: §4 · p. 21

Symmetric M-matrix Scaling

  • For symmetric nonnegative A, a diagonal scaling makes ((1 + ε)sI − A) SDD with high probability.The symmetric specialization uses an SDD solver.Source: §4 · p. 22

5 Finding Top Eigenvalue and Eigenvector of Positive Matrices

The section develops nearly linear-time algorithms for the Perron problem through M-matrix scaling and decision procedures. It also shows how to obtain approximate eigenvalues and eigenvectors without knowing the eigenvector condition-number bound in advance.

5 Finding Top Eigenvalue and Eigenvector of Positive Matrices

  • The section uses M-matrix scaling to develop nearly linear-time algorithms for the top eigenvalue and eigenvectors of non-negative matrices.The algorithms reduce the Perron problem to M-matrix decision and scaling procedures.Source: §5 · p. 22

5.1 The M-matrix Decision Problem

  • MMatrix-Decide either certifies that I − A is not an M-matrix or finds positive scalings making M_ε RCDD, assuming a bound K on the left and right Perron-vector condition numbers.The procedure checks potential failure modes, including nonpositive scalings and excessive iterations or solve times.Source: §5.1 · p. 23

5.2 Perron problem

  • Given K and an interval containing ρ(A), Find-Perron-Value returns an upper estimate less than (1 + ε)ρ(A).Its recursive steps reduce the interval size by a constant factor while preserving the spectral-radius bracket.Source: §5.2 · p. 25

5.2.1 Approximate top eigenvectors

  • Approximate Perron vectors are obtained by estimating the top eigenvalue and using M-matrix scaling to approximate vectors derived from a shifted inverse.The section states that approximately solving M-matrix systems can generate approximate top eigenvectors.Source: §5.2.1 · pp. 26–27

5.3 Fix for not knowing K

  • For a non-negative irreducible matrix A, Algorithm 9 runs in ˜O(m) time with high probability in n, computing s > 0 and positive left and right vectors such that (1−δ)ρ(A) < s ≤ ρ(A).K = Θ(κ(v_l) + κ(v_r)), where v_l and v_r are the left and right Perron vectors of A.Source: §5.3 · p. 30

6 Applications

The applications section uses M-matrix methods for economic input-output systems, Katz centrality, singular vectors, and random-walk graph kernels. It also describes how the framework handles sparse input when a derived matrix may be dense.

6 Applications

  • The section applies M-matrix methods to applications including Katz centrality, Leontief equations, singular vectors, and random-walk graph kernels.These applications include direct uses of the methods and cases that use the framework’s flexibility.Source: §6 · p. 31

6.1 Leontief Equations

  • The input-output equilibrium equations are (I − A)x = d, and the M-matrix decision and scaling algorithms check the Hawkin-Simons condition and approximate production rates.The passage states that the condition is equivalent to I − A being an M-matrix.Source: §6.1 · p. 31

6.2 Katz Centrality

  • The M-matrix solver gives a nearly linear-time algorithm for computing Katz centralities, whose vector satisfies v = αAv + b.Here A is the weighted adjacency matrix and α < ρ(A).Source: §6.2 · pp. 31–32

6.3 Left and Right Top Singular Vectors

  • A nearly linear-time M-matrix solver yields an algorithm for the top singular value and associated singular vectors of a non-negative matrix.The section notes that a tighter analysis for the symmetric case gives better bounds with fewer polylogarithmic factors.Source: §6.3 · pp. 32–33

6.4 Graph Kernels

  • Random-walk graph kernels reduce to inverting I − λW× and can be computed in nearly linear time in the size of W× when ∥λW×∥ < 1.The M-matrix decision algorithm can also check whether a given W× defines a valid kernel.Source: §6.4 · p. 35

8 M-matrix Facts

This section collects M-matrix properties used throughout the paper, including their relation to positive diagonal scalings and RCDD matrices.

8 M-matrix Facts

  • For M = sI − A with non-negative A, positive left and right vectors that make XMY RCDD certify that M is an M-matrix.Conversely, for an M-matrix, vectors x and y satisfying My > 0 and M⊤x > 0 produce an RCDD scaling.Source: §8 · p. 38
  • If an M-matrix has positive left and right scalings that make LMR RCDD, the symmetrized, diagonally transformed matrix is positive definite.The proof uses that S + S⊤ is symmetric diagonally dominant and applies the Gershgorin disk theorem.Source: §8 · pp. 38–39
  • For a non-negative matrix B, its infinity norm equals the largest row sum, max_i (B1)_i.Source: §8 · p. 39

9 Proofs for Section 4

These proofs establish bounds for regularized M-matrix systems and specify a symmetric scaling that yields an SDD matrix.

9 Proofs for Section 4

  • For M-matrix M and α ≥ 0, solving (M + αI)r = w with entries of w in [1, 2] gives a coordinatewise lower bound on r.The proof derives the bound from non-negativity of A when M = I − A.Source: §9 · p. 39
  • The proof bounds norms of the scaled regularized system using bounds on its left and right scaling vectors.It combines bounds for S_α and its inverse to obtain the stated norm control.Source: §9 · pp. 40–41
  • For symmetric A with ρ(A) < 1, the stated construction returns a positive diagonal V such that V[(1 + ε)I − A]V is SDD.Source: §9 · p. 42

10 Scaling Symmetric M-matrices

The section simplifies M-matrix scaling for symmetric inputs and gives its running time using SDD solvers. It also applies the scaling to solve symmetric M-matrix systems.

10 Scaling Symmetric M-matrices

  • For symmetric nonnegative A with ρ(A)<s, SymMMatrix-Scale computes diagonal V making V((1+ε)sI−A)V SDD with high probability.The theorem states that the algorithm runs in time, but the supplied passage does not include the time expression.Source: §10 · p. 42
  • An iterate v satisfying ||Mv−1||∞≤1/2 guarantees VMV is SDD, validating the output scaling.The proof assumes the approximate solutions returned by SDDSolve are valid; it states that the algorithm succeeds with high probability.Source: §10 · pp. 43–44
  • The initial scaling takes O(m log n), while each α stage uses O(log(nκ(M))) iterations and the stages repeat log(1/ε) times.Each iteration requires an O(m)-time matrix-vector product, a query to Z taking Tsolve time, and O(n) additional work.Source: §10 · pp. 44–45
  • For M=I−A with symmetric nonnegative A and ρ(A)<1, the method finds x with ||Mx−b||2≤ε||b||2.The corollary gives a running-time expression, but it is not present in the supplied passage.Source: §10 · p. 45

11 Factor Width 2 Matrices

For factor width 2 matrices, the section constructs a related symmetric M-matrix and uses its scaling to obtain a symmetric diagonally dominant system for solving the original system.

11 Factor Width 2 Matrices

  • Scaling M′ gives diagonal V for which both VM′V and VMV are symmetric diagonally dominant, so the original system can use an SDD solver.The passage also notes the same approach can be applied to asymmetric matrices with RCDD solvers.Source: §11 · p. 46
  • For factor width 2 M, changing the signs of off-diagonal entries to form M′ with M′ii=Mii makes M′ an M-matrix.The stated construction uses M′ij=−|Mij| for i≠j.Source: §11 · pp. 45–46
  • Factoring M as BᵀB with at most two nonzeros per row lets the proof construct a positive semidefinite symmetric Z-matrix, hence an M-matrix.The construction changes row-entry signs in B to obtain B′; (B′)ᵀB′ has off-diagonal entries at most −|Mij|.Source: §11 · p. 46
Loading 1810.02348v1…