The University of Adelaide
You are here » Home » People directory
Text size: S | M | L
Printer Friendly Version
September 2018
MTWTFSS
     12
3456789
10111213141516
17181920212223
24252627282930
       

Mr Rhys Bowden

Doctor of Philosophy student

Honours graduate

 

Office: 666 | Telephone: +61 8 8313 1605


Research seminars

TitleSeries
Modelling computer network topologies through optimisationPostgraduate Seminar

Doctoral thesis

Application of compressed sensing to network measurement and routing


Honours thesis

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.