A dissertation submitted to the Faculty of Science, University of the Witwatersrand, Johannesburg, in fulfilment of requirements for the degree of Master of Science. Johannesburg, 2016. / The l1-norm solution to an under-determined system of linear equations y = Ax is the
sparsest solution to the system. In digital signal processing this mathematical problem is
known as compressive sensing. Compressive sensing provides a mathematical framework for
sampling and reconstructing an analogue signal at a rate far lower than the rate provided
by the standard information theory. The reconstruction from few samples is possible using
non-linear optimization algorithms provided that the signal is sparse and the sensing matrix
in incoherent. The major algorithmic challenge in compressive sensing is to efficiently and
effectively find sparse solutions from minimal measurements. General purpose optimization
algorithms are not suitable for solving non-differentiable l1-minimization problem.
In this dissertation, we survey the major practical algorithms for nding l1-norm solution
of under-determined linear system of equations. Specific attention is paid to computational
issues, in which individual methods tends to perform well. We propose a hybrid algorithm
that combines complementary strengths of the fixed-point method and the interior-point
method. The strong feature of the xed-point method is its speed, while the strength of
the interior-point method is accuracy. The hybrid algorithm combine the two methods in
a probabilistic manner. The algorithm tends to prioritise a method that is efficient and
robust. The computational performance of the hybrid algorithm is tested on simple signal
reconstruction problems. The hybrid algorithm is shown to produce similar recoverability of
sparse solution as that of the xed-point method and the interior-point method. Furthermore
the proposed hybrid algorithm is comparative in terms of speed and accuracy with existing
methods. / LG2017
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:wits/oai:wiredspace.wits.ac.za:10539/21638 |
| Date | January 2016 |
| Creators | Sejeso, Matthews Malebogo |
| Source Sets | South African National ETD Portal |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | Online resource (viii, 100 leaves), application/pdf |
Page generated in 0.0019 seconds