text:
\subsection{Head Approximation Algorithm}
\label{sec:head}
First, we develop a head approximation algorithm for the CEMD model.
Ideally, we would have an \emph{exact} projection algorithm $H$ mapping arbitrary signals to signals in $\Mmodel_{k,B}$ with the guarantee $\norm{H(x)}_p = \max_{\Omega \in \Msupports_{k,B}} \norm{x_\Omega}_p$.
However, this appears to be a hard problem. Instead, we propose an
efficient greedy algorithm satisfying the somewhat looser requirements of a head
approximation oracle
(Definition~\ref{def:headapproxoracle}).
Specifically, we develop an algorithm that performs the following task:
given an arbitrary signal $x$, find a support $\Omega \in \Msupports_{O(k),O(B \log k)}$ such that
$\norm{x_\Omega}_p^p \geq c \max_{\Gamma\in \Msupports_{k,B}} \norm{x_\Gamma}_p^p$, where $c > 0$ is a fixed constant.

As before, we interpret our signal $x$ as a matrix $X \in \R^{h\times w}$.
Let $\OPT$ denote the largest sum of coefficients achievable with a support in $\Msupports_{k,B}$, i.e., $\OPT = \max_{\Omega \in \Msupports_{k,B}} \norm{x_\Omega}_p^p$.
For a signal $x \in \Mmodel_{k,B}$, we interpret the support of $x$ as a set of $s = k/w$ paths from the leftmost to the rightmost column in $X$.
Our method proceeds by greedily finding a set of paths that cover a large sum of signal coefficients.
We can then show that the coefficients covered by these paths are a constant fraction of the optimal coefficient sum $\OPT$.

\begin{definition}[Path in a matrix]\label{def:matrixpath}
Given a matrix $X \in \R^{h\times w}$, a path $r \subseteq [h] \times [w]$ is a set of $w$ locations in $X$ with one location per column, i.e., $\abs{r} = w$ and $\bigcup_{(i,j) \in r} j = [w]$.
The weight of $r$ is the sum of amplitudes on $r$, i.e., $w_{X,p}(r) = \sum_{(i,j)\in r} \abs*{X_{i,j}}^p \, $.
The EMD of $r$ is the sum of the EMDs between locations in neighboring columns.
Let $j_1, \ldots, j_w$ be the locations of $r$ in columns 1 to $w$.
Then,
$\EMD(r) = \sum_{i=1}^{w-1} \abs{j_i - j_{i+1}} \, .$
\end{definition}

\begin{algorithm}[!t]
\caption{Head approximation algorithm}
\label{alg:headapproxbasic}
\begin{algorithmic}[1]
\Function{HeadApprox}{$X, k, B$}
\State $X^{(1)} \gets X$
\For{$i  \gets 1, \ldots, s$}
\State Find the path $r_i$ from column 1 to column $w$ in $X^{(i)}$ that maximizes $w^{(i)}(r_i)$ and
\Statex uses at most EMD-budget $\floor{\frac{B}{i}}$.
\State $X^{(i + 1)} \gets X^{(i)}$
\For{$(u,v)  \in r_i $}
\State $X^{(i+1)}_{u,v} \gets 0$
\EndFor
\EndFor
\State \textbf{return} $\bigcup_{i = 1}^{s} r_i$
\EndFunction
\end{algorithmic}
\end{algorithm}

Trivially, we have that a path $r$ in $X$ is a support with $w_{X,p}(r) = \norm{X_r}_p^p$ and $\EMD(r) = \EMD(\supp(X_r))$.
Therefore, we can iteratively build a support $\Omega$ by finding $s$ paths in $X$.
Algorithm~\ref{alg:headapproxbasic} contains the description of \textsc{HeadApprox}.
We show that \textsc{HeadApprox} finds a constant fraction of the amplitude sum of the best support while only moderately increasing the size of the model.
For simplicity, denote $w(r) := w_{X,p}(r)$, and $w^{(i)}(r) := w_{X^{(i)},p}(r)$.
We obtain the following result:

\begin{theorem}
\label{thm:headapproxbasic}
Let $p \geq 1$ and $B' = \ceil{H_s} B$, where $H_s = \sum_{i=1}^s 1/i$ is the $s$-th harmonic number.
Then \textsc{HeadApprox} is a $((\frac{1}{4})^{1/p}, \Msupports_{k,B}, \Msupports_{k, B'}, p)$-head-approximation oracle.
\end{theorem}
\begin{proof}
Let $\Omega$ be the support returned by $\textsc{HeadApprox}(X, k, B)$ and let $\Omega_\OPT \in \Msupports_{k,B}$ be an optimal support.
We can always decompose $\Omega_\OPT$ into $s$ disjoint paths in $X$.
Let $t_1, \ldots, t_s$ be such a decomposition with $\EMD(t_1) \geq \EMD(t_2) \geq \ldots \geq \EMD(t_s)$.
Note that $\EMD(t_i) \leq \floor{\frac{B}{i}}$: otherwise $\sum_{j=1}^i \EMD(t_i) > B$ and since $\EMD(\Omega_\OPT) \leq B$ this would be a contradiction.
Since $\Omega$ is the union of $s$ disjoint paths in $X$, $\Omega$ has column-sparsity $s$.
Moreover, we have $\EMD(\Omega) = \sum_{i=1}^s \EMD(r_i) \leq \sum_{i=1}^s \floor{\frac{B}{i}} \leq \ceil{H_s} B .$
Therefore, $\Omega \in \Msupports_{k,B'}^+$.

When finding path $r_i$ in $X^{(i)}$, there are two cases:
\begin{description}[font=\normalfont]
\item[Case 1:] $w^{(i)}(t_i) \leq \frac{1}{2} w(t_i)$, i.e., the paths $r_1, \ldots, r_{i-1}$ have already covered more than half of the coefficient sum of $t_i$ in $X$.
\item[Case 2:] $w^{(i)}(t_i) > \frac{1}{2} w(t_i)$, i.e., there is still more than half of the coefficient sum of $t_i$ remaining in $X^{(i)}$.
Since $\EMD(t_i) \leq \floor{\frac{B}{i}}$, the path $t_i$ is a candidate when searching for the optimal path $r_i$ and hence we find a path $r_i$ with $w^{(i)}(r_i) > \frac{1}{2} w(t_i)$.
\end{description}
Let $C = \{i \in [s] \; | \; \text{case 1 holds for } r_i\}$ and $D = \{i \in [s] \; | \; \text{case 2 holds for } r_i\}$ (note that $C = [s] \setminus D$).
Then we have
\begin{equation}
\begin{split}
\norm{X_\Omega}_p^p = \sum_{i=1}^s w^{(i)}(r_i)
& = \sum_{i \in C} w^{(i)}(r_i) + \sum_{i \in D} w^{(i)}(r_i) \\
& \geq \sum_{i \in D} w^{(i)}(r_i)
\geq \frac{1}{2} \sum_{i \in D} w(t_i) \label{eq:dsum} \, .
\end{split}
\end{equation}
For each $t_i$ with $i \in C$, let $E_i = t_i \cap \, \bigcup_{j < i} r_j$, i.e., the locations of $t_i$ already covered by some $r_j$ when searching for $r_i$.
Then we have
\begin{equation*}
\sum_{(u,v) \in E_i} |X_{u,v}|^p = w(t_i) - w^{(i)}(t_i) \geq  \frac{1}{2} w(t_i) \, ,
\end{equation*}
and
\begin{equation*}
\sum_{i \in C}\sum_{(u,v) \in E_i} |X_{u,v}|^p \geq  \frac{1}{2} \sum_{i \in C} w(t_i) \, .
\end{equation*}
The $t_i$ are pairwise disjoint, and so are the $E_i$.
For every $i \in C$ we have $E_i \subseteq \bigcup_{j=1}^s r_j$. Hence
\begin{equation}
\norm{X_\Omega}_p^p = \sum_{i=1}^s w^{(i)}(r_i)
\geq \sum_{i \in C}\sum_{(u,v) \in E_i} |X_{u,v}|^p
\geq  \frac{1}{2} \sum_{i \in C}  w(t_i) \,.
\label{eq:csum}
\end{equation}
Combining Equations \ref{eq:dsum} and \ref{eq:csum} gives:
\begin{align*}
2 \norm{X_\Omega}_p^p \; \geq & \; \frac{1}{2} \sum_{i \in C}  w(t_i) + \frac{1}{2} \sum_{i \in D} w(t_i)  = \frac{1}{2} \OPT \\
\norm{X_\Omega}_p \; \geq & \; \parens{\frac{1}{4}}^{1/p} \max_{\Omega' \in \Msupports_{k,B}} \norm{X_{\Omega'}}_p \; .
\end{align*}
\end{proof}

\begin{theorem}
\label{thm:headapproxtime}
\textsc{HeadApprox} runs in $O(s  n  B  h)$ time.
\end{theorem}
\begin{proof}
Observe that the running time of \textsc{HeadApprox} depends on the running time of finding a path with maximum weight for a given EMD budget.
The search for such a path can be performed by \emph{dynamic programming} over a graph with $w h B = n B$ nodes, or equivalently ``states'' of the dynamic program.\footnote{We use the terminology ``states'' here to distinguish the dynamic program from the graph we will introduce in Section \ref{sec:tail}.}
Each state in the graph corresponds to a state in the dynamic program, i.e., a location $(i, j) \in [w] \times [h]$ and the current amount of EMD already used $b \in \{0, 1, \ldots, B\}$.
At each state, we store the largest weight achieved by a path ending at the corresponding location $(i,j)$ and using the corresponding amount of EMD budget $b$.
Each state has $h$ outgoing edges to the states in the next column (given the current location, the decision on the next location also fixes the new EMD amount).
Hence the time complexity of finding one largest-weight path is $O(n B h)$ (the state space has size $O(n B)$ and each update requires $O(h)$ time).
Since we repeat this procedure $s$ times, the overall time complexity of \textsc{HeadApprox} is $O(s n B h)$.
\end{proof}

We can achieve an arbitrary constant head-approximation ratio by combining \textsc{HeadApprox} with \textsc{BoostHead} (see Section \ref{sec:boosting}).
The resulting algorithm has the same time complexity as \textsc{HeadApprox}.
Moreover, the sparsity and EMD budget of the resulting support is only a constant factor larger than $k$ and $B'$.

config: arxiv