\section{Proposed Algorithm: \brassens{}} 
\label{sec:algo}

In the following, we assume that the input matrix $M$ is $k$-sparse $r$-separable.
Our algorithm, called \brassens{}\footnote{It stands for \brassens{} Relies on Assumptions of Separability and Sparsity for Elegant NMF Solving.}, is presented formally in \cref{alg:ssnmf}.
\input{41pseudocode-ssnmf}

On \cref{alg:dosnpa} we apply the original SNPA to select the exterior vertices; it is computationally cheap and ensures that these vertices are properly identified. The symbol $\infty$ means that SNPA stops only when the residual error is zero. For the noisy case, we replace the condition $R \neq 0$ by $R > \delta$, where $\delta$ is a user-provided noise-tolerance threshold.

Then, we adapt SNPA to impose a $k$-sparsity constraint on $H$: 
  the projection step (\cref{alg:snpa-proj} of \cref{alg:snpa}) is replaced by a $k$-sparse projection step that imposes the columns of $H$ to be $k$-sparse by solving~\eqref{eq:sparseproj}. 
  We call \emph{kSSNPA} this modified version of SNPA. 
  Note that, if $k = r$, kSSNPA reduces to SNPA.  

On \cref{alg:dokssnpa} we apply kSSNPA to select candidate interior vertices. 
We provide it with the set $\mathcal{J}$ of exterior vertices so that they do not need to be identified again.
kSSNPA extracts columns of $M$ as long as the norm of the residual \mbox{$\| M-M(:,\mathcal{J}') H \|_F$} is larger than zero.
At this point, all vertices have been identified: the exterior vertices have been identified by SNPA, while the interior vertices have been identified by kSSNPA because we will assume that they are not $k$-sparse combinations of any other data points; see  Section~\ref{sec:analysis} for the details. 

Hence, the error will be equal to zero if and only if all vertices have been identified.
However, some selected interior points may not be interior vertices, because the selection step of kSSNPA chooses the point that is furthest away from the \emph{$k$-sparse hull} of the selected points, that is, the union of the convex hulls of the subsets of $k$ already selected points.
For example, in \cref{fig:intvertex}, if $W_1$, $W_2$, and $W_3$ are selected, the $k$-sparse hull is composed of the 3 segments  $[W_1,W_2]$, $[W_2,W_3]$, and $[W_3,W_1]$.

In this case, although only point~$W_4$ is a interior vertex, point~$M_1$ is selected before point~$W_4$, because it is located further away from the $k$-sparse hull.

On \crefrange{alg:loop}{alg:addtoJ}, we apply a postprocessing to the selected points by checking whether they are $k$-sparse combinations of other selected points; this is a $k$-sparse NNLS problem solved with \arbo{}~\cite{nadisicexact}.
If they are, then they cannot be vertices and they are discarded, such as point~$M_1$ in Figure~\ref{fig:intvertex} which belongs to the segment $[W_1,W_4]$.

Note that this ``postprocessing'' could be applied directly to the whole data set by selecting data points as the columns of $W$ if they are not $k$-sparse combinations of other data points. 
However, this is not reasonable in practice, as it is equivalent to solving $n$ times a $k$-sparse NNLS subproblem in $n-1$ variables. 
The kSSNPA step can thus be interpreted as a safe screening technique, similarly as done in~\cite{el2010safe} for example, in order to reduce the number of candidate atoms from all the columns of $M$ to a subset  $\mathcal{J}'$ of columns. In practice, we have observed that kSSNPA is very effective at identifying good candidates points; see Section~\ref{sec:xp-synth}.
{"config": "arxiv", "file": "2006.07553/arXiv SSNMF/40algo.tex"}