Not all 2D filters are actually separable. A 2D filter is only separable if its rows/columns are linearly dependent (i.e., each column is a scalar multiple of other columns and each row is a scalar multiple of the other rows). If you look at the Gaussian filter on this slide, you can see how every column is just a scaled version of the 1D column vector of the left side of the equation. The scalar coefficients come from each of the scalar values in the row vector beside it. The same applies for all the rows.
Considering this, now imagine you took the SVD decomposition of an arbitrary 2D filter (that is not separable). You could approximate the 2D filter by only taking the u, v vector pair corresponding to the highest singular value. That is, you just take (sigma1 * u1 @ v1.T), where sigma1 is the largest singular value, and u1, v1 are corresponding basis vectors in the orthonormal U and V bases of the SVD decomposition. This 2D matrix will be an outer-product, so it is definitely separable. If the singular value corresponding to it is way larger than all the other singular values in the SVD decomposition, then we know that the outer-product is a good approximation for the original matrix. That means that convolving with it won't give that much different of an answer than convolving with the original filter. Plus, because it is separable, we can also take advantage of the runtime boost!
xiaochy
This slide reminds me of what I have learnt in CS182 last semester about adding lora layer to finetune a model. Basically instead of finding all the weights of a big matrix, we decompose the matrix into two smaller matrices and find the weights of both matrices, which greatly reduces the number of parameters we want to update during training.
Not all 2D filters are actually separable. A 2D filter is only separable if its rows/columns are linearly dependent (i.e., each column is a scalar multiple of other columns and each row is a scalar multiple of the other rows). If you look at the Gaussian filter on this slide, you can see how every column is just a scaled version of the 1D column vector of the left side of the equation. The scalar coefficients come from each of the scalar values in the row vector beside it. The same applies for all the rows.
Considering this, now imagine you took the SVD decomposition of an arbitrary 2D filter (that is not separable). You could approximate the 2D filter by only taking the u, v vector pair corresponding to the highest singular value. That is, you just take (sigma1 * u1 @ v1.T), where sigma1 is the largest singular value, and u1, v1 are corresponding basis vectors in the orthonormal U and V bases of the SVD decomposition. This 2D matrix will be an outer-product, so it is definitely separable. If the singular value corresponding to it is way larger than all the other singular values in the SVD decomposition, then we know that the outer-product is a good approximation for the original matrix. That means that convolving with it won't give that much different of an answer than convolving with the original filter. Plus, because it is separable, we can also take advantage of the runtime boost!
This slide reminds me of what I have learnt in CS182 last semester about adding lora layer to finetune a model. Basically instead of finding all the weights of a big matrix, we decompose the matrix into two smaller matrices and find the weights of both matrices, which greatly reduces the number of parameters we want to update during training.