\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[a4paper, total={6in, 8in}]{geometry}
\usepackage{amsmath, amsfonts}
\usepackage{hyperref, graphicx}

\title{CSCI 145 Problem 19: Characterizing Convolution}
\author{} % TODO: Put your name here
\date{\today}

\begin{document}
\maketitle

\subsection*{Submission Instructions}
Please upload your work to Gradescope by \textbf{11:59pm on DATE}. % TODO: date
\begin{itemize}
\item Turn in a single PDF of \textit{handwritten} solutions. Typed (including \LaTeX) solutions will not be accepted.
\item Problems are grouped into three-week \textbf{cycles}. Once per cycle, you will meet with the grader and present the solution to \emph{one} problem from that cycle, selected at random when you arrive; bring your work and be ready to explain any of them.
\end{itemize}

\newpage \section*{Problem 19: Characterizing Convolution \hfill \textnormal{2 points}}

Let $\mathbf{S}\in\mathbb R^{n\times n}$ cyclically shift a vector by one coordinate, and let $\mathbf{T}\in\mathbb R^{n\times n}$ be linear. Prove that
$$
\mathbf{T}\mathbf{S}=\mathbf{S}\mathbf{T}
\quad\Longleftrightarrow\quad
\mathbf{T}=\sum_{j=0}^{n-1} w_j\mathbf{S}^j
\quad\text{for some }\mathbf{w}\in\mathbb R^n.
$$
Use your result to explain why weight sharing is the general linear solution to circular shift equivariance. Then connect the representation to the supplied Fourier formula: identify the eigenvalue associated with each Fourier vector and explain why the resulting algorithm applies $\mathbf{T}$ in $O(n\log n)$ rather than $O(n^2)$ time. State what changes at an ordinary image boundary where shifts are not circular.

\paragraph{Results you may use.}
For $\omega=e^{-2\pi i/n}$, the Fourier vectors $\mathbf{f}_m$ satisfy $\mathbf{S}\mathbf{f}_m=\omega^m\mathbf{f}_m$. Consequently, every polynomial in $\mathbf{S}$ is diagonalized by the Fourier basis. The discrete Fourier transform of $\mathbf{w}$ is the vector with entries
$$
\hat w_m=\sum_{j=0}^{n-1}w_j\omega^{mj}.
$$
You may use complex vectors in this calculation. You may also quote that circular convolution can be computed by taking the Fourier transforms of the input and filter, multiplying their entries, and applying the inverse transform, with total cost $O(n\log n)$.

%\input{solutions/solution19}
\end{document}
