Dear Nadan,

Interesting question!

If we have a waveform and we want to convert it in the discrete time domain, we appy on it the sampling theory of Nyquit as stated in the question. This sampling rate is the minimum to reconstruct the waveform again. So, consequently for any waveform encoding fs=>2 fm, where fm is the maximum frequency contained in the waveform.Not only that but when quantising the samples every ample must be presented by n bit such that the quantiation error is negligibly small. This is called pcm coding.

From the other side analog signals containing  information and waveform sampled and quarantined have redundancy from the point of view of the information theory. As a consequence of this  the samples can be represented by a smaller number of bits than that for the waveform encoding called pcm encoding.

The redundancy can be partially eliminated by a process called prediction and using differential pcm.  There is a number of low losses  compression techniques for sound called hybrid coders like code excited linear predictive coding. Such codec can reproduce the waveform with allowed small portion of losses while reducing every sample to much less number of bits.

Video signal could be treated in the same way by means of video codecs.

under sampling will not preserve the waveform and such transformations can lead to signal compression but one may not be able to reconstruct the original waveform similar to linear predictive coders.

wish you success.

wish you success

@Andrez:

The implication of your answer could be "instead of having separate sampling and quantization  process, if we combine these two then we can recover signal in Sampling frequency less than twice the maximum frequency components.