## 4 Compressed Sensing Enabled Network Tomography
### Loss Estimation
Then, given the routing matrix \(\mathbf{A}\), a measured snapshot \(\mathbf{y}=[Y_{1}\;Y_{2}\ldots Y_{n_{p}}]^{\intercal}\) and the prior link state probabilities calculated in the previous step, the links that are currently congested (and not just simply their probabilities of congestion) can be located by solving Equation (9) for \(\mathbf{z}=[Z_{1}\;Z_{2}\ldots Z_{n_{c}}]^{\intercal}\). Given that Equation (9) has multiple solutions, the goal is to find the most likely one. Let \(\mathcal{P}_{\text{G}}\) denote the set of paths measured as being good (i.e., \(p_{i}\in\mathcal{P}_{\text{G}}\) when \(Y_{i}=0\)) and \(\mathcal{P}_{\text{C}}\) as the set of paths found to be congested (i.e., \(p_{i}\in\mathcal{P}_{\text{C}}\) when \(Y_{i}=1\)). The _reduced routing matrix_\(\mathbf{B}\) is obtained by removing from \(\mathbf{A}\) all rows that correspond to good paths and all columns that correspond to links in the good paths. Therefore, each row of \(\mathbf{B}\) represents a congested path and each column is a link that belongs to at least one congested path. Let \(\mathcal{E}_{B}\) denote the set of links represented by columns of \(\mathbf{B}\). Then, \(\mathbf{B}\) has dimensions \(|\mathcal{P}_{\text{C}}|\times|\mathcal{E}_{B}|\). The congested link identification problem is simplified to finding a set of links \(H\subseteq\mathcal{E}_{B}\), such that all congested paths are covered by at least one link in \(H\) and:  
\[\operatorname*{argmax}_{H\subseteq\mathcal{E}_{B}}\mathbb{P}_{\mathbf{q}}(H)= \operatorname*{argmax}_{H\subseteq\mathcal{E}_{B}}\sum_{k=1}^{|\mathcal{E}_{B }|}Z_{k}\;\log\left(\frac{q_{k}}{1-q_{k}}\right)=\operatorname*{argmin}_{H \subseteq\mathcal{E}_{B}}\sum_{k=1}^{|\mathcal{E}_{B}|}Z_{k}\;\log\left(\frac {1-q_{k}}{q_{k}}\right),\]In order to localize congested links and infer loss rates, the authors in [52] connect compressed sensing theory with Bayesian theory, in the sense that they propose a variation of the \(\ell_{1}\)_minimization_ method, the _weighted \(\ell_{1}\) minimization_ method, and use MAP estimation based on the prior congestion probability to determine the weights. Prior probabilities of link congestion are determined from path congestion probabilities based on Boolean algebra. By taking the expectations and logarithms of Equation (9), \(n\) equations containing the prior probabilities \(q_{k}\) are obtained. Nevertheless, more equations are needed in order to determine \(q_{k}\). To that end, by combining different paths, new \(n(n-1)/2\) independent equations can be created, containing the joint probabilities that two or more paths are congested. Now, \(q_{k}\) can be determined. In practice, since the Boolean random variable which represents link state follows the Bernoulli distribution, \(q\) can be updated based on former diagnostic results, thus easing the expensive time consumption of computing prior probabilities, using the maximum likelihood estimator for Bernoulli distribution:  
\[\hat{q_{k}}=\frac{\text{congestion times of link }k}{\text{all diagnosis times}}. \tag{11}\]  
Based on Equation (10), the weights that will be used in the formulation of the _weighted \(\ell_{1}\) minimization_ method can be calculated as follows:  
\[\omega_{k}=\log\frac{(1-q_{k})}{q_{k}}. \tag{12}\]  
Having computed the weights, \(\omega_{k}\), _weighted \(\ell_{1}\) minimization_ can be formulated and solved:  
\[\widehat{\mathbf{X}}=\operatorname*{argmin}_{x}\sum_{k=1}^{n}\omega_{k}\Big{|} \mathbf{X}_{k}\Big{|}\quad\text{subject to }\mathbf{A}\mathbf{X}=\mathbf{Y}. \tag{13}\]  
The convex problem of Equation (13) can be recast as a linear problem and can be solved by any LP optimizer. Assuming that the routing matrix \(A\) can be represented as the adjacency matrix of an expander graph, the estimation that comes from Equation (13) can be upper bounded.