Frame permutation quantization (FPQ) is a new vector quantization technique
using finite frames. In FPQ, a vector is encoded using a permutation source
code to quantize its frame expansion. This means that the encoding is a partial
ordering of the frame expansion coefficients. Compared to ordinary permutation
source coding, FPQ produces a greater number of possible quantization rates and
a higher maximum rate. Various representations for the partitions induced by
FPQ are presented and reconstruction algorithms based on linear programming and
quadratic programming are derived. Reconstruction using the canonical dual
frame is also studied, and several results relate properties of the analysis
frame to whether linear reconstruction techniques provide consistent
reconstructions. Simulations for uniform and Gaussian sources show performance
improvements over entropy-constrained scalar quantization for certain
combinations of vector dimension and coding rate.