Compression algorithms specific to complex signals
Complex signals are a special case of multidimensonal signals (where the dimension is two).
A lossy approach tackling compression of multidimensional signals is vector quantization. A very good resource is the book:

"Vector Quantization and Signal Compression", 

co-authored by Robert M. Gray.

Vector Qquantization is a classic lossy source coding technique that is used to quantize $M$-dimensional source vectors into a set of $N$-dimensional code vectors which is referred to as the codebook, and $N&lt;M$. A scalar quantizer is a special case with $M = 1$.

A complex signal in general can be seen as two correlated sources. Of course, if you don't want to assume any correlation between the real and imaginary part, then the answer is trivial since the two sources can be compressed independently and separately (using the standard compression techniques of real signals).

If you are interested in information-theoretic aspects of lossy/lossless compression of correlated sources, Wyner-Ziv and Slepian-Wolf coding are the keywords. These schemes are refereed to as distributed source coding schemes. However, since a complex signal can be modeled by two correlated sources, they can be considered here as well.

Finally, for analytic signals, since the imaginary/real part can be perfectly reconstructed from the other one by using the hilbert transform, the compression problem boils down to compression of a single real signal, for which there are plenty of standard schemes.



In response to the updated question:

Loyd algorithm generalized for vector quentization is referred to as LBG Algorithm (abbreviation of the name of the authors of the following paper)

Y. Linde, A. Buzo and R. Gray, "An Algorithm for Vector Quantizer Design," in IEEE Transactions on Communications, vol. 28, no. 1, pp. 84-95, Jan 1980.

It was again extended in 1989 for entropy coded vector quantization:

P. A. Chou, T. Lookabaugh, R. M. Gray, “Entropy constrained vector quantization,” IEEE Transactions on Signal Processing, vol. 37, no. 1, pp. 3142, January 1989.

I can recommend visiting www.data-compression.com/vq for a descent explanation of the scheme. It works in a simple way: 


Divide the vector space. 
Update the partitions.
Repeat the procedure for the new partitions until the quantization error is acceptable. 


At the end, all data points that belong to a partition are quantized to the coordination of the center of partitions. The centers are indexed such that to represent all quantized values only the index is stored/sent.  

Animated illustration from the same website for 2D Gaussian source:

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;