Sejeso, Matthews Malebogo2017-01-182017-01-182016Sejeso, 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>http://hdl.handle.net/10539/21638A 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.Online resource (viii, 100 leaves)enSignal processing--Digital techniques--MathematicsHybrid computer simulationThesis