Short-Time Fourier Transform (STFT) in Signal Processing - Time & Space Complexity

Time Complexity: Short-Time Fourier Transform (STFT)

O(n log m)

Understanding Time Complexity

We want to understand how the time it takes to compute the Short-Time Fourier Transform changes as the input signal gets longer.

How does the work grow when we analyze more data?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np
from scipy.signal import stft

# x is the input signal array
# fs is the sampling frequency
f, t, Zxx = stft(x, fs=fs, nperseg=window_size, noverlap=overlap)

This code splits the signal into overlapping windows and computes the Fourier transform on each window.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Computing the Fourier transform on each window segment.
• How many times: Once for each window, which depends on the signal length and window step size.

How Execution Grows With Input

As the input signal length grows, the number of windows increases roughly in proportion to the signal length.

Input Size (n)	Approx. Operations
10,000 samples	About 10,000 / (window_size - overlap) Fourier transforms
100,000 samples	About 10 times more Fourier transforms than 10,000 samples
1,000,000 samples	About 100 times more Fourier transforms than 10,000 samples

Pattern observation: The total work grows roughly linearly with the input size.

Final Time Complexity

Time Complexity: O(n \log m)

This means the time grows roughly proportional to the input length times the cost of each Fourier transform on a window of size m.

Common Mistake

[X] Wrong: "The STFT time grows only with the number of windows, ignoring the cost of each Fourier transform."

[OK] Correct: Each window requires a Fourier transform, which itself takes time proportional to the window size times a logarithm factor, so ignoring this underestimates the total time.

Interview Connect

Understanding how STFT scales helps you explain performance in real signal analysis tasks, showing you can think about both data size and algorithm steps clearly.

Self-Check

"What if we doubled the window size while keeping the signal length the same? How would the time complexity change?"

Practice

1. What is the main purpose of the Short-Time Fourier Transform (STFT) in signal processing?

easy

A. To compress a signal into fewer data points

B. To analyze how frequencies change over time in a signal

C. To remove noise from a signal completely

D. To convert a signal from digital to analog form

Solution

1. Step 1: Understand STFT function

   STFT breaks a signal into small time segments and finds frequency content in each segment.

2. Step 2: Identify main goal

   This helps us see how frequencies change over time, unlike a normal Fourier transform which shows overall frequencies.

3. Final Answer:

   To analyze how frequencies change over time in a signal -> Option B

4. Quick Check:

   STFT = frequency changes over time [OK]

Hint: STFT = frequency analysis in short time windows [OK]

Common Mistakes:

• Confusing STFT with noise removal
• Thinking STFT compresses data
• Mixing STFT with analog conversion

2. Which of the following is the correct Python function call to compute STFT using the scipy library on a signal array named signal with a window size of 256?

easy

A. scipy.stft(signal, nperseg=256)

B. scipy.stft(signal, window=256)

C. scipy.signal.fft(signal, window=256)

D. scipy.signal.stft(signal, nperseg=256)

Solution

1. Step 1: Recall scipy STFT syntax

   The STFT function is in scipy.signal as stft(), and the window size is set by nperseg parameter.

2. Step 2: Match correct syntax

   scipy.signal.stft(signal, nperseg=256) uses scipy.signal.stft(signal, nperseg=256), which is correct syntax.

3. Final Answer:

   scipy.signal.stft(signal, nperseg=256) -> Option D

4. Quick Check:

   Correct function and parameter = scipy.signal.stft(signal, nperseg=256) [OK]

Hint: Use scipy.signal.stft with nperseg for window size [OK]

Common Mistakes:

• Using scipy.stft instead of scipy.signal.stft
• Confusing fft() with stft()
• Passing window size as 'window' instead of 'nperseg'

3. Given the following Python code using scipy.signal.stft, what is the shape of the output array Zxx?

import numpy as np
from scipy.signal import stft
signal = np.sin(2 * np.pi * 5 * np.linspace(0, 1, 100))
f, t, Zxx = stft(signal, nperseg=20)
print(Zxx.shape)

medium

A. (11, 6)

B. (20, 5)

C. (50, 2)

D. (10, 10)

Solution

1. Step 1: Calculate frequency bins

   With nperseg=20, frequency bins = nperseg//2 + 1 = 10 + 1 = 11 rows.

2. Step 2: Calculate time segments

   Signal length=100, window=20, default no overlap means about 6 segments (100/20 rounded up).

3. Final Answer:

   (11, 6) -> Option A

4. Quick Check:

   Zxx shape = (freq bins, time segments) = (11, 6) [OK]

Hint: Output shape = (nperseg/2+1, number of windows) [OK]

Common Mistakes:

• Confusing nperseg with output shape rows
• Miscounting time segments
• Assuming output shape equals input length

4. Identify the error in this STFT code snippet and choose the correct fix:

from scipy.signal import stft
signal = [1, 2, 3, 4, 5]
f, t, Zxx = stft(signal, nperseg=10)
print(Zxx)

medium

A. Error: nperseg is larger than signal length; fix by setting nperseg=5

B. Error: signal must be a numpy array; fix by converting signal to np.array(signal)

C. Error: stft requires window parameter; fix by adding window='hann'

D. No error; code runs fine

Solution

1. Step 1: Check nperseg vs signal length

   Signal length is 5, but nperseg=10 is larger, which causes a warning or error in scipy.

2. Step 2: Fix nperseg value

   Set nperseg to 5 or less to match signal length and avoid error.

3. Final Answer:

   Error: nperseg is larger than signal length; fix by setting nperseg=5 -> Option A

4. Quick Check:

   nperseg ≤ signal length to avoid error [OK]

Hint: nperseg must not exceed signal length [OK]

Common Mistakes:

• Ignoring nperseg size error
• Thinking signal type causes error
• Adding unnecessary window parameter

5. You want to analyze a music clip with fast-changing notes using STFT. Which combination of window size and overlap will give you better time resolution but less frequency resolution?

hard

A. Large window size with high overlap

B. Large window size with low overlap

C. Small window size with high overlap

D. Small window size with low overlap

Solution

1. Step 1: Understand window size effect

   Small window size improves time resolution but reduces frequency resolution.

2. Step 2: Understand overlap effect

   High overlap keeps time segments close, improving time detail further.

3. Final Answer:

   Small window size with high overlap -> Option C

4. Quick Check:

   Better time resolution = small window + high overlap [OK]

Hint: Small window + high overlap = better time detail [OK]

Common Mistakes:

• Choosing large window for better time resolution
• Ignoring overlap effect
• Assuming low overlap improves time resolution