How does filter separability optimize Gaussian blur and its complexity?
This tests if you know a 2D Gaussian separates into two 1D convolutions. A strong answer gives complexity as O(N^2 K^2) dropping to O(N^2 K) for an N-by-N image and K-by-K kernel. A red flag is claiming all kernels are separable or omitting dimensions.
What's really being asked
This tests whether you understand the mathematical structure of the Gaussian kernel and how linear algebra translates into algorithmic speedups in real image processing pipelines. The interviewer cares if you can move beyond memorizing Gaussian blur and explain why it is fast, how separability works, and how to express concrete complexity.
The full answer
First, state that a 2D Gaussian kernel G of size K by K is separable because it is the outer product of two 1D Gaussian vectors, meaning G of x comma y equals g of x times g of y. Second, explain the optimization: instead of convolving the image with a K-by-K 2D kernel, you perform two sequential 1D convolutions, one horizontal and one vertical, each of length K. Third, quantify the speedup. For an N-by-N image and a K-by-K kernel, the naive 2D convolution requires roughly N squared times K squared multiplications and additions. After decomposition, the cost drops to roughly 2 times N squared times K operations, which is O of N squared K. Fourth, mention practical implications: this is why large Gaussian blurs are feasible in real-time graphics and computer vision, whereas a non-separable large kernel would be prohibitive.
The mistakes people make
A major red flag is claiming that any kernel can be decomposed this way. Only kernels that are rank-one matrices are separable, and the Gaussian happens to satisfy this because of the multiplicative property of the exponential function. Another red flag is giving complexity only as O of K squared versus O of K without referencing the image size N squared, since complexity must account for every pixel. Some candidates also confuse separability with sliding-window integral image tricks or box filter approximations; those are valid optimizations but they are not the same thing as exact separability.
What usually comes next
The interviewer may ask how you would prove a given kernel is separable. The answer is to check if the kernel matrix has rank one, which you can verify via Singular Value Decomposition and confirming only the first singular value is non-zero. They may also ask about border handling, such as whether zero-padding or edge replication affects the separability proof. It does not; the separability is a property of the kernel weights, independent of padding mode. Another follow-up is how to approximate a non-separable kernel: you can use SVD to keep the top few singular values and apply multiple separable passes, trading accuracy for speed.
A concrete example
Consider a 5-by-5 Gaussian kernel with sigma 1. The naive approach performs 25 multiplications and 24 additions per pixel. Using separability, you first convolve each row with a 5-tap 1D Gaussian, then convolve each column of the intermediate result with the same 1D Gaussian. That is 5 multiplications and 4 additions per pixel for the first pass, and another 5 multiplications and 4 additions for the second pass, totaling 10 multiplications and 8 additions. For a 4K image of roughly 8 million pixels, that is the difference between 200 million and 80 million multiplications, a 2.5x speedup that grows linearly with kernel size.
Interview question
What is the primary reason a 2D Gaussian blur can be computed in O(N²K) rather than O(N²K²) for an N×N image and K×K kernel?
- a.The kernel's circular symmetry permits skipping half the multiplications
- b.The Gaussian kernel is normalized so its coefficients sum to unity
- c.The convolution theorem allows FFT-based frequency domain multiplication
- d.The Gaussian kernel is a rank-one matrix expressible as the outer product of two 1D vectorsCorrect
Why? this is the answer
The Gaussian kernel is separable because it equals the outer product of two 1D Gaussians (a rank-one matrix), so two O(N²K) 1D passes replace one O(N²K²) 2D convolution. Using FFT is a distinct optimization, and neither normalization nor circular symmetry implies that a kernel can be decomposed into 1D passes.
Just read this? Test yourself on what you have been reading.
Read the original → en.wikipedia.org
- #computer-vision
- #image-processing
- #algorithms
- #linear-algebra
- #complexity-analysis
You just looked this up. Could you explain it out loud?
That is the part interviews actually test. Tezvyn takes questions like this one and gives you what the interviewer is really checking, the answer that lands, and the mistake that ends the conversation, in the four minutes before your next meeting.
The iPhone app is on the way
We are building it. Until it lands, nothing here is held back from you: every interview card, your saved cards, streaks and the job board all work in Safari, plus hundreds of free practice quizzes of thirty questions each. Sign in and it all carries over to the app the day it arrives.
Want it as an icon? Tap Share at the bottom of Safari, then Add to Home Screen. It opens full screen and the cards you have read stay available offline.
We are hiring for this. Open roles that interview on computer-vision — each one lists the topics its interview covers.
See open roles