Nyquist vs Curse of Dimensionality

Let us assume a specific definition for the dimension of a signal. According to this definition, an n dimensional signal is a function of n independent variables. Therefore, y = f(t) is a one dimensional signal since it has only one independent variable which is time (t). An image, I(x,y) is a two dimensional signal since it has two independent variables.

For one dimensional signal the theory which provides constraint to the minimum sampling rate is the Nyquist criterion. It says that, if the maximum frequency component of a band-limited signal be f , then the sampling rate for successful reconstruction of the signal has to be f_s \geq 2f . Now, if the part of signal that we are interested is 1 then the number of samples required for successful reconstruction of the signal be N_s \geq 2f*(1) = 2f

Now, consider the case of a two dimensional signal (e.g. image). In such case, the number of samples become 2*f_x *2*f_y = 2^2 *f_x*f_y. Notice that the more the dimensionality is increasing, the number of required samples is increasing exponentially. That is the phenomenon that happens in case of data with high dimensionality. This phenomenon is also known as curse of dimensionality.

Now questions:

  1. What is the maximum frequency component in case of image? Ofcourse there is no “time variable” in an image right? then what is the frequency mean in that case. The question can be placed in some other way too. What do we mean when we say about the frequency and phase components when we do a Fourier Transform of an image. Answer to this question is easy. But how should I answer the next?
  2. What is the equivalent of such criterion in case of the probability density function of an n dimensional random vector? I know each sample there is an n dimensional vector. But, analogically, what represents the “frequencies” in such case?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s