An l1-norm solution of under-determined linear algebraic systems using a hybrid method

Show simple item record

dc.contributor.author Sejeso, Matthews Malebogo
dc.date.accessioned 2017-01-18T07:16:00Z
dc.date.available 2017-01-18T07:16:00Z
dc.date.issued 2016
dc.identifier.citation Sejeso, Matthews Malebogo (2016) An l1-norm solution of under-determined linear algebraic systems using a hybrid method, University of Witwatersrand, Johannesburg, <http://wiredspace.wits.ac.za/handle/10539/21638>
dc.identifier.uri http://hdl.handle.net/10539/21638
dc.description 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. en_ZA
dc.description.abstract 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. en_ZA
dc.format.extent Online resource (viii, 100 leaves)
dc.language.iso en en_ZA
dc.subject.lcsh Signal processing--Digital techniques--Mathematics
dc.subject.lcsh Hybrid computer simulation
dc.title An l1-norm solution of under-determined linear algebraic systems using a hybrid method en_ZA
dc.type Thesis en_ZA
dc.description.librarian LG2017 en_ZA


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search WIReDSpace


Browse

My Account