Введение
Многомерный алгоритм данных (MP) - это алгоритм сплошного приближения, который находит "лучшее совпадение" проекций многомерных данных на размах более полного (т.е. избыточного) словаря. Основная идея заключается в приблизительном представлении сигнала из пространства Гильберта как взвешенной суммы конечного числа функций (называемых атомами), взятых из Приближение с атомами имеет форму, где th - столбец матрицы и является скалярным весовым фактором (амплитудой) для атома. Вместо этого, сопоставление преследования выбирает атомы по одному за раз, чтобы максимально (жадно) уменьшить ошибку приближения. Это достигается путем нахождения атома, который имеет наибольшее внутреннее произведение с сигналом (при условии, что атомы нормализованы), вычитая из сигнала приближение, которое использует только этот один атом, и повторяя процесс до тех пор, пока сигнал не будет удовлетворительно разложен, т. е. норма остатка мала, где остаток после расчета и обозначается как Если быстро сходится до нуля, то для получения хорошего приближения к нулю требуется только несколько атомов Такие рассеянные представления желательны для кодирования и сжатия сигнала. Более точно, проблема редкости, которую соответствующая преследование предназначено приблизительно решить, где псевдо-норма (т.е. количество ненулевых элементов). В предыдущей нотации, ненулевые записи из решают проблему редкости точно NP трудно, поэтому используются методы приближения, такие как MP. Для сравнения рассмотрим представление преобразования Фурье о сигнале, которое можно описать с использованием терминов, приведенных выше, где словарь построен из синусоидальных базовых функций (самый маленький возможный полный словарь). Основным недостатком анализа Фурье в обработке сигналов является то, что он извлекает только глобальные особенности сигналов и не адаптируется к анализируемым сигналам.
Matching pursuit (MP) is a sparse approximation algorithm which finds the "best matching" projections of multidimensional data onto the span of an over complete (i. e., redundant) dictionary The basic idea is to approximately represent a signal from Hilbert space as a weighted sum of finitely many functions (called atoms) taken from An approximation with atoms has the form
where is the th column of the matrix and is the scalar weighting factor (amplitude) for the atom Normally, not every atom in will be used in this sum. Instead, matching pursuit chooses the atoms one at a time in order to maximally (greedily) reduce the approximation error. This is achieved by finding the atom that has the highest inner product with the signal (assuming the atoms are normalized), subtracting from the signal an approximation that uses only that one atom, and repeating the process until the signal is satisfactorily decomposed, i. e., the norm of the residual is small,
where the residual after calculating and is denoted by If converges quickly to zero, then only a few atoms are needed to get a good approximation to Such sparse representations are desirable for signal coding and compression. More precisely, the sparsity problem that matching pursuit is intended to approximately solve is
where is the pseudo norm (i. e. the number of nonzero elements of ). In the previous notation, the nonzero entries of are Solving the sparsity problem exactly is NP hard, which is why approximation methods like MP are used. For comparison, consider the Fourier transform representation of a signal this can be described using the terms given above, where the dictionary is built from sinusoidal basis functions (the smallest possible complete dictionary). The main disadvantage of Fourier analysis in signal processing is that it extracts only the global features of the signals and does not adapt to the analysed signals By taking an extremely redundant dictionary, we can look in it for atoms (functions) that best match a signal .
Приложения
Соответствующее преследование применяется для кодирования сигналов, изображений и видео, представления и распознавания форм, кодирования 3D-объектов и в междисциплинарных приложениях, таких как мониторинг состояния структуры. Было показано, что он лучше, чем DCT-кодирование для низких скоростей передачи данных как по эффективности кодирования, так и по качеству изображения. Основная проблема с поиском совпадений - это вычислительная сложность кодера. В базовой версии алгоритма, большой словарь должен быть найден при каждой итерации. Улучшения включают использование приблизительных словарных представлений и субоптимальных способов выбора наилучшего совпадения при каждой итерации (атомное извлечение). Алгоритм сопоставления используется в MP/SOFT, методе моделирования квантовой динамики. MP также используется в обучении словарю. В этом алгоритме атомы изучаются из базы данных (в целом, природные сцены, такие как обычные изображения), а не выбираются из общих словарей. Очень недавнее применение МП - его использование в кодировании линейных вычислений для ускорения вычисления матричных векторных произведений.
Расширения
Популярное расширение Matching Pursuit (MP) - это его ортогональная версия: Orthogonal Matching Pursuit (OMP). Основное отличие от МП заключается в том, что после каждого шага все до сих пор извлеченные коэффициенты обновляются путем вычисления ортогональной проекции сигнала на подпространство, охватываемое набором атомов, выбранных до сих пор. Это может привести к результатам лучше, чем стандартный MP, но требует большего количества вычислений. Было показано, что OMP обладает стабильностью и гарантированной работой при определенных ограниченных условиях изометрии. Инкрементальный многопараметрический алгоритм (IMP), опубликованный за три года до MP, работает так же, как и OMP. Расширения, такие как Multichannel MP и Multichannel OMP, позволяют обрабатывать многокомпонентные сигналы. Очевидным расширением Matching Pursuit является использование нескольких позиций и масштабов, путем увеличения словаря до уровня волновой базы. Это можно сделать эффективно, используя оператор свертывания без изменения основного алгоритма. Соответствующее преследование связано с областью сжатого восприятия и было расширено исследователями в этом сообществе. Примечательными расширениями являются Orthogonal Matching Pursuit (OMP), Stagewise OMP (StOMP), компрессионное выборка соответствия преследования (CoSaMP), обобщенный OMP (gOMP) и Multipath Matching Pursuit (MMP).