Office: 666 | Telephone: +61 8 8313 1605
Application of compressed sensing to network measurement and routing
Recovering sparse vectors exactly from few linear measurements
Given a system of n linear equations in m variables, with m > n, there are infinitely many possible solutions. However, if the solution is also required to be sparse, i.e. to have few nonzero elements, then the problem is changed drastically. In many such cases, there is a unique sparsest solution. Undetermined systems of linear equations occur in many fields, including sparse representation and compressed sensing in signal processing; computation on large data sets; error correcting codes and privacy preserving computation. Often the most desirable solutions are sparse solutions. In some cases this is because they require the fewest resources to implement, or the least space to remember. In other cases it's because they most accurately represent the behaviour of signals. Unfortunately, even if a unique sparsest solution does exist, ?nding it might not be computationally tractable. In general, ?nding the unique sparsest solution x is NP-hard, requiring combinatorial optimisation. Fortunately, there are several common ways to attempt to reach the sparsest solution quickly, including greedy methods, ?1 -minimisation (basis pursuit) and fast combinatorial algorithms. As the performance bounds for these algorithms are mostly given with undetermined constants or relatively weak inequalities, it is interesting to consider what occurs in practice for speci?c values of m and n. We test their the success rates and speed for these algorithms over a range of practical values. Comparing the algorithms, we see that Orthogonal Matching Pursuit is both faster to implement and substantially faster to run, but requires a greater number of measurements to retrieve the signal than ?1 -minimisation.