The Mailman Algorithm: A Note on Matrix Vector Multiplication

Abstract

Given an m x n matrix A we are interested in applying it to a real vector x epsilon Rn in less then the straightforward O(mn) time. For an exact, deterministic computation at the very least all entrees in A must be accessed, requiring O(mn) operations and matching the running time of naively applying A to x. However, we claim that if the matrix contains only a constant number of distinct values, then reading the matrix once in O(mn) steps is sufficient to preprocess it such that any subsequent application to vectors requires only O(mn= log(max{m,ng}) operations. Theoretically our algorithm can improve on recent results for dimensionality reduction and practically it is useful (faster) even for small matrices.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2008
Accession Number
ADA482124

Entities

People

  • Edo Liberty
  • Steven W. Zucker

Organizations

  • Yale University

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Alphabets
  • Compressed Sensing
  • Computer Science
  • Computers
  • Dimensionality Reduction
  • Electrical Engineering
  • Information Operations
  • Mathematics
  • Numbers
  • Polynomials
  • Postal Service
  • Preprocessing
  • Probability
  • Universities

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Linear Algebra
  • Neural Network Machine Learning.
  • Theoretical Analysis.