Sparse Signal Recovery über reskaliertes Matching Pursuit

Wir schlagen den Rescaled Matching Pursuit (RMP) Algorithmus vor, um spärliche Signale in hochdimensionalen euklidischen Räumen wiederherzustellen. Der RMP-Algorithmus hat eine geringere Rechenkomplexität als andere gierige Algorithmen, wie den Orthogonal Matching Pursuit (OMP). Wir zeigen, dass, wenn die eingeschränkte Isometrie-Eigenschaft erfüllt ist, die obere Grenze des Fehlers zwischen dem ursprünglichen Signal und seiner Annäherung abgeleitet werden kann. Darüber hinaus beweisen wir, dass der RMP-Algorithmus mit hoher Wahrscheinlichkeit den richtigen Support spärlicher Signale aus zufälligen Messungen finden kann. Unsere numerischen Experimente bestätigen ebenfalls diese Schlussfolgerung und zeigen, dass RMP stabil gegenüber Rauschen ist. Daher ist der RMP-Algorithmus ein geeignetes Verfahren zur Wiederherstellung spärlicher Signale.