The Art of Divide and Conquer


Divide and conquer seem the most widely used strategy to attack hard problems. The use of this idea and similar approaches are ample in every discipline. In this post, let’s look at how this concept is a cornerstone in analyzing signals and systems.

Consider the case of audio signals. We can think of them as vibrations of air molecules that eventually reach our eardrums. The tiny fluctuations made by these vibrations stimulate the sensors inside our ears. I remember reading about how our hearing system had thousands of tiny hairs that respond to different frequencies in different ways.

Right here itself we can see that nature uses thousands of tiny hairs to listen to different frequencies, rather than using a single one for all.

The Crux Idea

The crux idea here is to break down a complex thing into tiny pieces each of which we can understand well. Then leverage that understanding to attack the bigger problem. You might recollect how we created arbitrary shapes in our childhood using the lego building blocks.

Lego as divde and conquer
Lego example

When it comes to audio signals, if we visualized the pressure fluctuations as a graph, we will see complex fluctuations. How can we break it down into its fundamental components so that we can understand each piece perfectly and use that information to process the original signal?.

Fourier Transforms

Fourier transform is one of the methods to do this. There are also different methods other than Fourier methods. Within the Fourier method itself, there are variations depending upon whether the signal is a periodic one, discrete vs. continuous, etc.

What Fourier transform does is to approximate the given input signal as a sum of different sine and cosine waves of various amplitudes and frequencies. Although the reconstruction may not be 100% perfect, most of the time the slight differences are not noticeable as per human perception. The following figure shows how a square wave can be approximated using a group of sinusoids of various amplitudes and frequencies.

Fourier transform as divide and conquer

Now the next important question is why sinusoidal waves?

Back to Old School Calculus

You might remember taking derivatives and integrals of mathematical functions in your college calculus classes. Whether you have noticed it or not one important observation here is that for sinusoidal functions, the result of derivatives or integrals always results in another sinusoidal function.

This property is unique to only sinusoidal function. For example $\frac{d(sinx)}{dx} = cos(x)=sin(x+\frac{\pi}{2})$. This means we started with a sine wave and we ended up with a sinewave shifted in time.

There is only the amplitude scaling or shrinking and time-shifting is happening. The important point is that the shape of the input signal remains intact. Can you show me any other signal or function which has this property?

The complex exponential ($e^{j\omega}$) is another example. But we can consider it also as a sum of sine and cosine components according to the Euler identity ($e^{j\omega} = cos(\omega)+i*sin(\omega)$).

Analogies from Linear Algebra

You might have learned that matrices do the linear transformation to vectors in abstract vector space. There are techniques like Principal Component Analysis (PCA) which identify vectors that does not change its shape while doing the matrix transformation.

One of the major applications of linear algebra is to do dimensionality reduction of complex data. The way it is done is by identifying the principal components and projecting the data to them. The major components capture the maximum variance and we stop approximating at an acceptable level.

This is reminiscent of the square wave approximation example where the initial components contribute to the shape of square waves mostly and the later ones add tiny finishing touches.

The analogy here is that the principal components do not change their direction. It only stretches or shrinks. This means if we visualize the vector as a function, again its shape remains intact, and it just gets streached or shrinked.

Real-life Applications

Knowingly or unknowingly we use these techniques in various domains and applications. Communication systems use these to send and receive signals. When we use MP3 files for music and JPEG files for images, we are using an approximation to the original content using such major fundamental components.

The only major requirement or hurdle in front of us is in figuring out a streamlined procedure to identify these fundamental components. So the next time you are trying to lose weight or trying to improve your analytical skills, it is worth spending some time to think about the fundamental component of that process. Who knows, we might be lucky to figure out the secret ingredients to our aim!.

Leave a Comment

Your email address will not be published. Required fields are marked *