The Data Compression Conference (DCC) 2013 is happening right now, and tomorrow I’ll be presenting a new paper that I co-authored with Shantanu Rane titled “Efficient Coding of Signal Distances Using Universal Quantized Embeddings” [1]. This is continuation of earlier work on coding of distances [2].

I am quite excited about this work for two reasons:

1. It is the first practical application of my earlier work on universal quantization [3], which I think provides a very promising coding framework for a number of applications.
2. The results show a remarkable improvement over previous results. We have managed to demonstrate bitrate reduction of more than 33% over our earlier work in [2] and more than 50% over existing methods.

The paper provides a framework to analyze the performance of embeddings when used to evaluate distances in the embedding domain. As it turns out, the embeddings derived from the universal quantization methods in [3] allow the system designer to decide the range of distances to be preserved by the embedding and use fewer bits if the range is smaller. In many inference applications—such as ones using nearest-neighbor search—what matters is that small distances are preserved, not necessarily larger ones. Thus appropriately designing the embedding results to significant saving in bits. This saving is a great example of information scalability, where the coding complexity scales with the amount of information one needs to extract.

The figure below demonstrates the performance of our method in an image retrieval problem. It shows the probability of correct retrieval using a query image as a function of the bitrate used to code each descriptor extracted from the query image. You can see the paper for more details on the retrieval scheme, but that scheme is not really the point of the paper; our focus is on the embedding-based coding method and the analysis. The black lines demonstrate the performance of universal embeddings, while the colored lines the performance of earlier work (including ours).

@inproceedings{BR_DCC13,
  Address =   {Snowbird, UT},
  Author =   {Boufounos, P. T. and Rane, S.},
  Booktitle =   {Proc. Data Compression Conference (DCC)},
  Pdf =     {http://boufounos.com/Publications/BR_DCC2013.pdf},
  doi =          {10.1109/DCC.2013.33},
  url =          {http://doi.org/10.1109/DCC.2013.33},
  Month =   {March 20-22},
  Title =   {Efficient Coding of Signal Distances Using Universal Quantized Embeddings},
  Year =   {2013}
}

@inproceedings{LRB_MMSP12,
  Address =   {Banff, Canada},
  Author =   {Li, M. and Rane, S. and Boufounos, P. T.},
  Booktitle =   {IEEE 14th International Workshop on Multimedia Signal Processing (MMSP)},
  Month =   {Sept. 17-19},
  Pdf =     {http://boufounos.com/Publications/LRB_MMSP12.pdf},
  url =     {http://doi.org/10.1109/MMSP.2012.6343406},
  doi =     {10.1109/MMSP.2012.6343406},
  Title =   {Quantized embeddings of scale-invariant image features for mobile augmented reality},
  Year =   {2012},
  Note =   {Top 10% paper award}
}

@article{B_TIT_12,
  Arxivurl =   {http://arxiv.org/abs/1009.3145},
  Author =   {Boufounos, P. T.},
  Doi =     {10.1109/TIT.2011.2173899},
  Journal =   {IEEE Trans. Info. Theory},
  Month =   {March},
  Number =   {3},
  Pages =   {1861-1872},
  Volume =   {58},
  Pdf =          {http://boufounos.com/Publications/B_UniversalScalarQuantization.pdf},
  Title =   {Universal Rate-Efficient Scalar Quantization},
  Url =     {http://doi.org/10.1109/TIT.2011.2173899},
  Year =   {2012}
}