IN GREEDY PURSUIT OF NEW DIRECTIONS: (NEARLY) ORTHOGONALMATCHING PURSUIT BY DIRECTIONAL OPTIMISATION

摘要

Matching Pursuit and orthogonal Matching Pursuit arerngreedy algorithms used to obtain sparse signal approximations.rnOrthogonal Matching Pursuit is known to offer betterrnperformance, but Matching Pursuit allows more efficient implementations.rnIn this paper we propose novel greedy Pursuitrnalgorithms based on directional updates. Using a conjugaterndirection, the algorithm becomes a novel implementationrnof orthogonal Matching Pursuit, with computationalrnrequirements similar to current implementations based onrnQR factorisation. A significant reduction in memory requirementsrnand computational complexity can be achieved by approximatingrnthe conjugate direction. Further computationalrnsavings can be made by using a steepest descent direction.rnThe two resulting algorithms are then comparable to MatchingrnPursuit in their computational requirements, their performancernis however shown to be closer to that of orthogonalrnMatching Pursuit with the (slightly slower) approximate conjugaterndirection based approach outperforming the gradientrndescent method.