## 4 Compressed Sensing Enabled Network Tomography
### Delay Estimation  
In [41], the authors apply concepts from compressed sensing and expander graphs to the link delay estimation problem. Specifically, they determine the conditions on the routing matrices under which the underlying networks are \(k\)-identifiable; that is, for every exactly \(k\)-sparse vector \(\mathbf{X}\), the equation \(\mathbf{Y}=\mathbf{A}\mathbf{X}\) is uniquely solvable. By combining concepts from compressed sensing and expander graphs, the authors relax the \(k\)-identifiability expansion condition of a network, such that its routing matrix does not have to be the bi-adjacency matrix of a regular bipartite graph but the bi-adjacency matrix of the union of disjoint expander graphs with error parameter \(\epsilon\leq\frac{1}{4}\). Under this relaxed condition, the \(k\)-sparse link vector can be estimated via \(\ell_{1}\) minimization. This relaxation expands the list of identifiable networks with bounded estimation error by 30%. Another work based on expander graphs is [44], where the authors demonstrate that the routing matrix corresponding to a full tree with \(q\) branches on each node excluding leaves can be used as a measurement matrix in CS for recovering \(k\)-sparse signals with \(k=q/2\) and a bounded expected estimation error. If the tree is not full, they present a heuristic method that proceeds by adding virtual nodes. Therefore, \(\ell_{1}\)-minimization can be employed for network topologies that can be interpreted as a series of trees, either full or not full. In [45], the synchronization error is taken under consideration and it is treated as additive, zero-mean white Gaussian noise. In addition, link delays are assumed to follow an exponential distribution, whose parameter value reveals whether \(\mathbf{X}_{t}\) is sparse or not. Based on these two assumptions and in order to account for measurement errors too, a variation of \(\ell_{1}\)-\(\ell_{2}\)_optimization_ using Maximum A-Posteriori (MAP) estimation is proposed. An unconstrained \(\ell_{1}\)-\(\ell_{2}\)_optimization_ problem is defined:  
\[\hat{\mathbf{X}}=\underset{x}{\text{argmin}}\left(\frac{1}{2}\left\|\mathbf{Y}-\mathbf{A} \mathbf{X}\right\|_{2}^{2}+\lambda\left\|\mathbf{X}\right\|_{1}\right), \tag{6}\]  
where \(\lambda\) is a function of sparsity and noise. In particular, if vector \(\mathbf{X}\) is assumed to follow a Laplace prior distribution, the optimization problem of Equation (6) leads to a MAP estimator. Since link delay does not follow the Laplace distribution as it cannot be negative, the constraint that \(\mathbf{X}\) is positive leads to \(\mathbf{X}\) following the exponential distribution. Under the assumption that the components \(X_{i}\) are independent, the authors look for the vector \(\hat{\mathbf{X}}\) that maximizes the conditional probability of link delay vector \(\mathbf{X}\) given the measurement \(\mathbf{Y}\) and noise. They apply the Bayes Rule and replace the \(\left\|\mathbf{X}\right\|_{1}=\sum_{i=1}^{n}\left|X_{i}\right|\) by the weighted form \(\mathbf{c}^{\top}\mathbf{X}=\sum_{i=1}^{n}c_{i}\left|X_{i}\right|\). Thus, Equation (6) is transformed to the _constrained \(\ell_{1}\)-\(\ell_{2}\) optimization_ problem:  
\[\hat{\mathbf{X}}=\operatorname*{argmin}_{x}\left(\frac{1}{2\sigma^{2}}\left\|\mathbf{Y }-\mathbf{A}\mathbf{X}\right\|_{2}^{2}+\mathbf{c}^{\top}\mathbf{X}\right),\ \ \text{ subject to }\mathbf{X}>0, \tag{7}\]  
where \(c_{i}=\frac{1}{\tau_{i}}\). Simulation experiments have shown that the _constrained \(\ell_{1}\)-\(\ell_{2}\) optimization_ outperforms the original one, achieving smaller \(\ell_{2}\) norm estimation error and higher detection probability. Yet, the need for an efficient algorithm to solve Equation (7) remains. Since delay tomography depends on accurate end-to-end time measurements, clock synchronization is a requirement that restricts the number of suitable end-to-end paths over which the measurements can be made. In order to overcome this limitation, an approach called _reflective network tomography_ is proposed in [46].