Least Squares Ranking on Graphs, Hodge Laplacians, Time Optimality, and Iterative Methods

摘要: Given a set of alternatives and some pairwise comparison values, ranking is least squares computation on graph. The graph vertices are the alternatives, with weighted oriented edge between each pair for which there score. orientations arbitrary. edges may be sparse or dense. basic idea very simple old { come up vertex potential such that dierence matches given data. Since an exact match will usually impossible, one settles matching data in sense. This formulation was rst described by Leake 1976 football teams [21]. residual can further analyzed discovering inconsistencies data, this leads to second problem. whole process formulated recently Jiang et al. as Hodge decomposition values [19]. problem, besides being important renement ranking, has other applications, economics In recent breakthrough paper, Koutis [20] showed symmetric diagonally dominant (SDD) linear systems solved time approaching optimality (we’ll refer their algorithm KMP solver). We show easy consequence result arbitrary graph, problem using solver. involves 2-Laplacian, dierent from Laplacian. It not been studied theoretical computer science literature. if 1-skeleton cell complex compact surface system matrix also SDD, implies via KMP. For all above cases we give bounds number conjugate gradient iterations required achieve error bound. graphs do boundaryless surface. same Laplacian dual If embedding does have boundary, then use Cauchy’s interlacing theorem solve patching holes case. These special computational topology, problems 2-norm version optimal homologous chain topology [10]. general cells lled in, is, general, dominant. Thus apply directly nothing known about its spectrum general. case best approach iterative Krylov method numerical results several choices. methods useful large where loss sparsity forming might storage issue. problem’s singular high dimensional kernel equal dimension homology independent spheres tetrahedra amongst cliques. work space orthogonal no modding required.