Greedy vector quantization

We investigate the greedy version of the LpLp-optimal vector quantization problem for an RdRd-valued random vector X∈Lp. We show the existence of a sequence (aN)N≥1(aN)N≥1 such that aNaN minimizes a↦‖min1≤i≤N−1|X−ai|∧|X−a|‖Lpa↦‖min1≤i≤N−1|X−ai|∧|X−a|‖Lp (LpLp-mean quantization error at level NN induced by (a1,…,aN−1,a)(a1,…,aN−1,a)). We show that this sequence produces LpLp-rate optimal NN-tuples a(N)=(a1,…,aN)a(N)=(a1,…,aN) (i.ei.e. the LpLp-mean quantization error at level NN induced by a(N)a(N) goes to 00 at rate N−1d). Greedy optimal sequences also satisfy, under natural additional assumptions, the distortion mismatch property: the NN-tuples a(N)a(N) remain rate optimal with respect to the LqLq-norms, p≤q