License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.44
URN: urn:nbn:de:0030-drops-147378
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14737/
Go to the corresponding LIPIcs Volume Portal

Bishnu, Arijit ; Ghosh, Arijit ; Mishra, Gopinath

Distance Estimation Between Unknown Matrices Using Sublinear Projections on Hamming Cube

pdf-format:
LIPIcs-APPROX44.pdf (1.0 MB)

Abstract

Using geometric techniques like projection and dimensionality reduction, we show that there exists a randomized sub-linear time algorithm that can estimate the Hamming distance between two matrices. Consider two matrices A and B of size n × n whose dimensions are known to the algorithm but the entries are not. The entries of the matrix are real numbers. The access to any matrix is through an oracle that computes the projection of a row (or a column) of the matrix on a vector in {0,1}ⁿ. We call this query oracle to be an Inner Product oracle (shortened as IP). We show that our algorithm returns a (1± ε) approximation to {D}_M (A,B) with high probability by making O(n/(√{{D)_M (A,B)}}poly(log n, 1/(ε))) oracle queries, where {D}_M (A,B) denotes the Hamming distance (the number of corresponding entries in which A and B differ) between two matrices A and B of size n × n. We also show a matching lower bound on the number of such IP queries needed. Though our main result is on estimating {D}_M (A,B) using IP, we also compare our results with other query models.

BibTeX - Entry

@InProceedings{bishnu_et_al:LIPIcs.APPROX/RANDOM.2021.44,
  author =	{Bishnu, Arijit and Ghosh, Arijit and Mishra, Gopinath},
  title =	{{Distance Estimation Between Unknown Matrices Using Sublinear Projections on Hamming Cube}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{44:1--44:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14737},
  URN =		{urn:nbn:de:0030-drops-147378},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.44},
  annote =	{Keywords: Distance estimation, Property testing, Dimensionality reduction, Sub-linear algorithms}
}

Keywords: Distance estimation, Property testing, Dimensionality reduction, Sub-linear algorithms
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Issue Date: 2021
Date of publication: 15.09.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI