## 4 Compressed Sensing Enabled Network Tomography  
Compressed sensing is an emerging field in signal/image processing that has recently made its appearance in the field of network tomography, gaining more ground ever since. It is based on the assumption that only a few network links are responsible for the end-to-end delays and/or losses, which provides prior information that the solution, i.e., the \(\mathbf{X_{t}}\) vector of the linear measurement model, is sparse (the only nonzero components of the vector are those corresponding to these \"bottleneck\" links). According to compressed sensing theory, if a vector is \(k\)-sparse (i.e., has \(k\) nonzero value elements), then we can precisely recover it with only \(\mathcal{O}(k\log\frac{n}{k})\) measurements, with \(n\) being the vector's dimension [39; 40]. In order to accurately estimate \(\mathbf{X_{t}}\) using _LP optimization_ (or a variation of this method when synchronization errors are taken under consideration), the routing matrix \(\mathbf{A}\) (often termed measurement matrix in the context of CS) needs to be constructed following some desirable (and conflicting) properties:  
1. enable accurate reconstruction of \(\mathbf{X_{t}}\) from \(\mathbf{Y_{t}}\) when \(\mathbf{X_{t}}\) is known to be sparse;
2. use fast decoding algorithm; and
3. make the least possible measurements (maximum achievable compression of \(\mathbf{A}\)) [41]. In order to ensure that the measurement paths are selected such that they meet the \(k\)_-identifiable condition_, i.e., the ability to recover the \(k\)-sparse vector \(\mathbf{X}_{t}\) from the end-to-end measurements \(\mathbf{Y_{t}}\) obtained over these measurement paths, different methods have been proposed. According to [42], whether one can recover a sparse vector \(\mathbf{X}_{t}\) from \(\mathbf{Y_{t}}\) by means of compressed sensing can be evaluated by the mutual coherence \(\mu(\mathbf{A})\), which is defined as the largest absolute norm inner product between different columns of \(\mathbf{A}\):  
\[\mu(\mathbf{A})=\max_{1\leqslant i,j\leqslant m,i\
eq j}\frac{\left|a_{i}^{T}a_{j} \right|}{\left\|a_{i}\right\|_{2}\left\|a_{j}\right\|_{2}}, \tag{4}\]where \(a_{i}\) is the \(i\)-th column of \(A\) and \(\left\|\cdot\right\|_{2}\) represents \(\ell_{2}\) norm defined as \(\left\|\mathbf{w}\right\|_{2}=\sum_{i=1}^{n}\left|w_{i}^{2}\right|^{1/2}\), with \(w_{i}\) being the components of vector \(\mathbf{w}\). The fact that the equation \(\mathbf{Y}_{t}=\mathbf{A}\mathbf{X}_{t}\) is ill-posed means that any vector \(\mathbf{X}_{t}\in\{\mathbf{X}_{0}+N(\mathbf{A})\}\) satisfies the equation, where \(N(\mathbf{A})\) is the null space of \(\mathbf{A}\) and \(\mathbf{X}_{0}\) is defined as the _true delay vector_ that needs to be obtained. If \(\mathbf{X}_{0}\) is (exactly) \(k\)-sparse and \(k<\frac{1}{2}(1+\frac{1}{\mu(\mathbf{A})})\), then \(\mathbf{X}_{0}\) can be determined by the \(\ell_{1}\)_optimization_:  
\[\hat{\mathbf{X}}=\underset{x}{\text{argmin}}\left\|\mathbf{X}\right\|_{1}\quad\text{ subject to}\ \ \mathbf{A}\mathbf{X}=\mathbf{Y}, \tag{5}\]  
where \(\left\|X\right\|_{1}=\sum_{i=1}^{n}\left|X_{i}\right|\) is the \(\ell_{1}\) norm of \(\mathbf{X}\). A collaborative and distributed framework according to which nodes cooperate with each other in order to monitor the status of the entire network (i.e., efficiently recover any \(k\)-sparse networked data vector) is presented in [43]. Every node, apart from its own measurements utilizes measurements generated by the rest nodes, with the goal of reducing the number of overall required measurements. To that end, all nodes have their own independent measurement matrices consisting of random walks initiated by themselves as well as random walks generated by other peers. The authors derive an upper bound for the number of measurements that each node must generate, such that the collaborative global view of the entire network is achieved. Based on that upper bound, an optimization method is proposed to minimize the total number of measurements.