We show how to test whether a graph with n vertices and m edges is a partial cube, and if so how to find a distance-preserving embedding of the graph into a hypercube, in the near-optimal time bound O(n^2), improving previous O(nm)-time solutions.
Every partial cube may be embedded in a distance-preserving way into an integer lattice @math of some dimension @math . One such labeling simply uses each bit of a bitvector labeling as a coordinate in @math ; however, some graphs may be embeddable into integer lattices of much lower dimension than their isometric dimension. For instance, a path graph can be embedded into @math , and given one-dimensional coordinates that accurately describe the graph distances, despite having an isometric dimension of @math . The of a partial cube is the minimum number @math for which the graph admits a distance-preserving embedding into @math . The lattice dimension, and an embedding of that dimension, may be found in polynomial time using an algorithm based on graph matching @cite_36 , but this algorithm depends on having as input a bitvector labeling and is slower than the algorithm we describe here, so it does not form the basis of an efficient partial cube recognition algorithm.
@cite_36
2784919006
This paper deals with two related problems, namely distance-preserving binary embeddings and quantization for compressed sensing . First, we propose fast methods to replace points from a subset @math , associated with the Euclidean metric, with points in the cube @math and we associate the cube with a pseudo-metric that approximates Euclidean distance among points in @math . Our methods rely on quantizing fast Johnson-Lindenstrauss embeddings based on bounded orthonormal systems and partial circulant ensembles, both of which admit fast transforms. Our quantization methods utilize noise-shaping, and include Sigma-Delta schemes and distributed noise-shaping schemes. The resulting approximation errors decay polynomially and exponentially fast in @math , depending on the embedding method. This dramatically outperforms the current decay rates associated with binary embeddings and Hamming distances. Additionally, it is the first such binary embedding result that applies to fast Johnson-Lindenstrauss maps while preserving @math norms. Second, we again consider noise-shaping schemes, albeit this time to quantize compressed sensing measurements arising from bounded orthonormal ensembles and partial circulant matrices. We show that these methods yield a reconstruction error that again decays with the number of measurements (and bits), when using convex optimization for reconstruction. Specifically, for Sigma-Delta schemes, the error decays polynomially in the number of measurements, and it decays exponentially for distributed noise-shaping schemes based on beta encoding. These results are near optimal and the first of their kind dealing with bounded orthonormal systems.