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

Simple item page
dc.contributor.authorSejeso, Matthews Malebogo
dc.date.accessioned2017-01-18T07:16:00Z
dc.date.available2017-01-18T07:16:00Z
dc.date.issued2016
dc.descriptionA 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.abstractThe 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.description.librarianLG2017en_ZA
dc.format.extentOnline resource (viii, 100 leaves)
dc.identifier.citationSejeso, 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.urihttp://hdl.handle.net/10539/21638
dc.language.isoenen_ZA
dc.subject.lcshSignal processing--Digital techniques--Mathematics
dc.subject.lcshHybrid computer simulation
dc.titleAn l1-norm solution of under-determined linear algebraic systems using a hybrid methoden_ZA
dc.typeThesisen_ZA
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
final_sub_matthews.pdf
Size:
2.54 MB
Format:
Adobe Portable Document Format
Description:
Main article
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
ETD Collection