We consider the ratelimited quantumtoclassical
optimal transport in terms of outputconstrained ratedistortion
coding for discrete quantum measurement systems with limited
classical common randomness. The main coding theorem provides the achievable rate region of a lossy measurement source
coding for an exact construction of the destination distribution
(or the equivalent quantum state) while maintaining a threshold
of distortion from the source state according to a generally
defined distortion observable. The constraint on the output space
fixes the output distribution to an i.i.d. predefined probability
mass function. Therefore, this problem can also be viewed
as informationconstrained optimal transport which finds the
optimal cost of transporting the source quantum state to the
destination state via an entanglementbreaking channel with
limited communication rate and common randomness.
more »
« less
This content will become publicly available on November 30, 2024
Estimating the RateDistortion Function by Wasserstein Gradient Descent 37th Conference on Neural Information Processing Systems (NeurIPS)
In the theory of lossy compression, the ratedistortion (RD) function R(D) describes how much a data source can be compressed (in bitrate) at any given level of fidelity (distortion). Obtaining R(D) for a given data source establishes the fundamental performance limit for all compression algorithms. We propose a new method to estimate R(D) from the perspective of optimal transport. Unlike the classic BlahutArimoto algorithm which fixes the support of the reproduction distribution in advance, our Wasserstein gradient descent algorithm learns the support of the optimal reproduction distribution by moving particles. We prove its local convergence and analyze the sample complexity of our RD estimator based on a connection to entropic optimal transport. Experimentally, we obtain comparable or tighter bounds than stateoftheart neural network methods on lowrate sources while requiring considerably less tuning and computation effort. We also highlight a connection to maximumlikelihood deconvolution and introduce a new class of sources that can be used as test cases with known solutions to the RD problem.
more »
« less
 NSFPAR ID:
 10505296
 Editor(s):
 A. Oh; T. Naumann; A. Globerson; K. Saenko; M. Hardt; S. Levine
 Publisher / Repository:
 Curran Associates, Inc.
 Date Published:
 Journal Name:
 37th Conference on Neural Information Processing Systems (NeurIPS)
 Volume:
 36
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


In many quantization problems, the distortion function is given by the Euclidean metric to measure the distance of a source sample to any given reproduction point of the quantizer. We will in this work regard distortion functions, which are additively and multiplicatively weighted for each reproduction point resulting in a heterogeneous quantization problem, as used for example in deployment problems of sensor networks. Whereas, normally in such problems, the average distortion is minimized for given weights (parameters), we will optimize the quantization problem over all weights, i.e., we tune or control the distortion functions in our favor. For a uniform source distribution in onedimension, we derive the unique minimizer, given as the uniform scalar quantizer with an optimal common weight. By numerical simulations, we demonstrate that this result extends to twodimensions where asymptotically the parameter optimized quantizer is the hexagonal lattice with common weights. As an application, we will determine the optimal deployment of unmanned aerial vehicles (UAVs) to provide a wireless communication to ground terminals under a minimal communication power cost. Here, the optimal weights relate to the optimal flight heights of the UAVs.more » « less

Technical Program Committee, 2021 IEEE (Ed.)Consider a finite set of multiple sources, described by a random variable with m components. Only k ≤ m source components are sampled and jointly compressed in order to reconstruct all the m components under an excess distortion criterion. Sampling can be that of a fixed subset A with A = k or randomized over all subsets of size k. In the case of random sampling, the sampler may or may not be aware of the m source components. The compression code consists of an encoder whose input is the realization of the sampler and the sampled source components; the decoder input is solely the encoder output. The combined sampling mechanism and rate distortion code are universal in that they must be devised without exact knowledge of the prevailing source probability distribution. In a Bayesian setting, considering coordinated singleshot sampling and compression, our contributions involve achievability results for the cases of fixedset, sourceindependent and sourcedependent random sampling.more » « less

As the size and amount of data produced by highperformance computing (HPC) applications grow exponentially, an effective data reduction technique is becoming critical to mitigating time and space burden. Lossy compression techniques, which have been widely used in image and video compression, hold promise to fulfill such data reduction need. However, they are seldom adopted in HPC datasets because of their difficulty in quantifying the amount of information loss and data reduction. In this paper, we explore a lossy compression strategy by revisiting the energy compaction properties of discrete transforms on HPC datasets. Specifically, we apply blockbased transforms to HPC datasets, obtain the minimum number of coefficients containing the maximum energy (or information) compaction rate, and quantize remaining nondominant coefficients using a binning mechanism to minimize information loss expressed in a distortion measure. We implement the proposed approach and evaluate it using six realworld HPC datasets. Our experimental results show that, on average, only 6.67 bits are required to preserve an optimal energy compaction rate on our evaluated datasets. Moreover, our knee detection algorithm improves the distortion in terms of peak signaltonoise ratio by 2.46 dB on average.more » « less

We address the problem of animated character motion representation and approximation by introducing a novel form of motion expression in a function space. For a given set of motions, our method extracts a set of orthonormal basis (ONB) functions. Each motion is then expressed as a vector in the ONB space or approximated by a subset of the ONB functions. Inspired by the static PCA, our approach works with the timevarying functions. The set of ONB functions is extracted from the input motions by using functional principal component analysis and it has an optimal coverage of the input motions for the given input set. We show the applications of the novel compact representation by providing a motion distance metric, motion synthesis algorithm, and a motion level of detail. Not only we can represent a motion by using the ONB; a new motion can be synthesized by optimizing connectivity of reconstructed motion functions, or by interpolating motion vectors. The quality of the approximation of the reconstructed motion can be set by defining a number of ONB functions, and this property is also used to level of detail. Our representation provides compression of the motion. Although we need to store the generated ONB that are unique for each set of input motions, we show that the compression factor of our representation is higher than for commonly used analytic function methods. Moreover, our approach also provides lower distortion rate.more » « less