 we add the constraint on the maximum of the coefficients.

General $\ell_1$ minimization problem to promote sparsity {#l1}
---------------------------------------------------------

In addition to the number of connected components, we assume that we know one representative of each component i.e. a node belonging to this component. This assumption is not so restrictive compared to traditional spectral clustering where the number of clusters is assumed to be known. If we do not exactly know a representative for each component, we can estimate them by first applying a rough partitioning algorithm or just an algorithm that aims to find hubs of very densely connected parts of the graph.

Let $I_{n-k+1},\dots, I_n$ be the row indices of the representative element of each component and let $\tilde{\mathcal{V}}_{1,k}^1 =\{v\in \mathcal{V}_{1,k}^0 : v_{I_j}=1\}$ for all $j\in \left\{n-k+1, \dots,n   \right\}$. This is straightfoward to see that the indicator vector of the smallest component is solution of the following optimization problem.

\[prop4\] The minimization problem ($\mathcal{P}_1$)

$\underset{v\in \tilde{\mathcal{V}}_{1,k}^1 }{\arg\min}  {\|v\|}_1 $

has a unique solution given by $\textbf{1}_{C_{n-k+1}}$.

\[proof2\] We recall that $\|v\|_1=\sum\limits_{i=1}^n |v_i|$. Let $v \in \tilde{\mathcal{V}}_k^1$. Therefore, as $\textbf{1}_{C_{n-k+1}} \in \mathcal{V}_{1,k}^0$, $v$ can be decomposed as $v=\sum\limits_{j=n-k+1}^n \alpha_j \textbf{1}_{C_j}$ where $\alpha=(\alpha_{n-k+1},\dots ,\alpha_n)\in \mathbb{R}^k \  $ and there exists $ j \in \left\{n-k+1, \dots, n \right\} ,  \  \alpha_j \ne 0$.

The connected components of sizes $c_{n-k+1},\dots, c_n$ are sorted in increasing order of size. Therefore, $\|v\|_1=\alpha_{n-k+1} c_{n-k+1}+\dots +\alpha_n c_n$. The solution of ($\mathcal{P}_1$) is given by the vector in $\tilde{\mathcal{V}}_{1,k}^1$ that satisfies $\|v\|_{+\infty}$ and with the smallest $\ell_1$-norm such that $\alpha=(\alpha_{n-k+1} , 0, \dots, 0)$ where $\alpha_{n-k+1}=1$.

To simplify and without