To reduce space and time complexity we use restricted (or “windowed”) self-attention [1]}, which saves both space and time by replacing global computation with local computation. We partition the \(h\times w\)  patchified image into \(r\times r\)  patch non-overlapping windows and compute self-attention independently within each of these windows. This windowed self-attention has \(O(r^2hw)\)  space and time complexity (from \(O(r^4)\)  per-window complexity and \(h/r\times w/r\)  windows). We set \(r\)  to the global self-attention size used in pre-training (, \(r=14\)  is typical).
