Kissing to Find a Match: Efficient Low-Rank Permutation Representation

• URL: http://arxiv.org/abs/2308.13252v1
• Date: Fri, 25 Aug 2023 08:59:03 GMT
• Title: Kissing to Find a Match: Efficient Low-Rank Permutation Representation
• Authors: Hannah Dr\"oge, Zorah L\"ahner, Yuval Bahat, Onofre Martorell, Felix Heide, Michael M\"oller
• Abstract summary: We propose to tackle the curse of dimensionality of large permutation matrices by approximating them using low-rank matrix factorization, followed by a nonlinearity. We demonstrate the applicability and merits of the proposed approach through a series of experiments on a range of problems.
• Score: 33.880247068298374
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Permutation matrices play a key role in matching and assignment problems across the fields, especially in computer vision and robotics. However, memory for explicitly representing permutation matrices grows quadratically with the size of the problem, prohibiting large problem instances. In this work, we propose to tackle the curse of dimensionality of large permutation matrices by approximating them using low-rank matrix factorization, followed by a nonlinearity. To this end, we rely on the Kissing number theory to infer the minimal rank required for representing a permutation matrix of a given size, which is significantly smaller than the problem size. This leads to a drastic reduction in computation and memory costs, e.g., up to $3$ orders of magnitude less memory for a problem of size $n=20000$, represented using $8.4\times10^5$ elements in two small matrices instead of using a single huge matrix with $4\times 10^8$ elements. The proposed representation allows for accurate representations of large permutation matrices, which in turn enables handling large problems that would have been infeasible otherwise. We demonstrate the applicability and merits of the proposed approach through a series of experiments on a range of problems that involve predicting permutation matrices, from linear and quadratic assignment to shape matching problems.

Related papers

• A Simple Quantum Blockmodeling with Qubits and Permutations [0.0]
  We show how to solve blockmodeling on quantum computers. In the model, the measurement outcomes of a small group of qubits are mapped to indicate the fitness value.
  arXiv  Detail & Related papers  (2023-11-13T20:10:53Z)
• Dual-Matrix Domain-Wall: A Novel Technique for Generating Permutations by QUBO and Ising Models with Quadratic Sizes [0.14454647768189902]
  This paper introduces a novel permutation encoding technique called dual-matrix domain-wall. It significantly reduces the number of quadratic terms and the maximum absolute coefficient values in the kernel. We also demonstrate the applicability of our encoding technique to partial permutations and Quadratic Unconstrained Binary Optimization (QUBO) models.
  arXiv  Detail & Related papers  (2023-08-02T09:15:30Z)
• One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
  We propose a natural algorithm that involves imputing the missing values of the matrix $XTX$. We evaluate our algorithm on one-sided recovery of synthetic data and low-coverage genome sequencing.
  arXiv  Detail & Related papers  (2023-06-06T22:35:16Z)
• Sparse Factorization of Large Square Matrices [10.94053598642913]
  In this paper, we propose to approximate a large square matrix with a product of sparse full-rank matrices. In the approximation, our method needs only $N(log N)2$ non-zero numbers for an $Ntimes N$ full matrix. We show that our method gives a better approximation when the approximated matrix is sparse and high-rank.
  arXiv  Detail & Related papers  (2021-09-16T18:42:21Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  We present dimensionality reduction methods for non-PSD and square-roots" matrices. We show how these techniques can be used for multiple downstream tasks.
  arXiv  Detail & Related papers  (2021-06-16T04:07:48Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)
• Sketching Transformed Matrices with Applications to Natural Language Processing [76.6222695417524]
  We propose a space-efficient sketching algorithm for computing the product of a given small matrix with the transformed matrix. We show that our approach obtains small error and is efficient in both space and time.
  arXiv  Detail & Related papers  (2020-02-23T03:07:31Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  We study the performance of iterative sketching for least-squares problems. We show that the convergence rate for Haar and randomized Hadamard matrices are identical, andally improve upon random projections. These techniques may be applied to other algorithms that employ randomized dimension reduction.
  arXiv  Detail & Related papers  (2020-02-03T16:17:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.