# when is downsampling followed by upsampling shift invariant

i have a set of images that i need to send through an hourglass-type convolutional system.

I understand convolutions are shift-invariant, so i will ignore them

the question is then: If I downsample a signal by 2x, then upsample by 2x -- what constraints do i need to make sure the system is shift-invariant?

• You need to ensure you don’t have aliasing in the downsampling step, meaning apply a low pass filter first. I think that is all you need, though I’m not sure. Oct 30, 2021 at 3:03
• Can you put constraints on the signal? Oct 31, 2021 at 15:10
• For downsampling only signals: if ratio of shift to subsampling is integer. For downsampling convolutions: if both inputs are bandlimited. Proven here. May 31 at 23:33

In theory, strictly, never.

In theory, if you mean effectively shift invariant, then yes, if you low-pass filter the signal so that it is strictly bandlimited to $$\frac{1}{2} \mathrm{\frac{cycles}{pixel}}$$, then downsample, then reconstruct through a $$\frac{1}{2} \mathrm{\frac{cycles}{pixel}}$$ filter.

In practice, such a filter won't work. In a processing context where you assume a signal is of infinite extent, you can -- in theory -- construct a perfect bandlimiting filter, but it has an infinitely long impulse response. This is kind of difficult to realize in practice*.

In the context of a 2D signal that is finite both vertically and horizontally, you could make a filter with the required properties. It would have two problems:

1. The "infinitely long" character of the filter would turn into a high degree of bleeding of pixel values across the screen -- basically, with a finite field like this the edges of the screen appear mathematically** to butt against each other. So things happening in the right and left edges of the screen will bleed into each other. Ditto things happening in the top and bottom edges.
2. Any real filtering process won't be perfect. So your original image, converted, and your original image shifted by one and converted won't be exactly the same but for the shift.

* But easy to fake -- just make a "filter" that always returns zero, and if anyone asks, tell them you're waiting for the impulse response to start up.

** Sorta kinda -- there's a lot of ways to look at this.

• thanks for the explanation, it makes sense, i will have to figure out a new way to think about this -- applying band-limited filters on dense inputs quickly Nov 2, 2021 at 14:21

I understand convolutions are shift-invariant, so i will ignore them

input: $$[0\, 1\, 0\, 1\, 0\, 1\, …]$$
you then decimate by 2, convolve with a discrete filter of impulse response $$[1 \, 1]$$, and get constant zero or constant one, depending on whether your shift was even or off numbers of samples.
This is a special case of a signal that is insufficiently bandlimited (to be specific, this is a signal that has a frequency component at DC, and one at $$f_{\text{sample}}/2$$, and that second frequency is just an $$\varepsilon$$ too high) from Tim's excellent answer.