This paper has been withdrawn by Ali Çivril
No PDF available, click to view other formats
Abstract:The problem of sparse approximation and the closely related compressed sensing have received tremendous attention in the past decade. Primarily studied from the viewpoint of applied harmonic analysis and signal processing, there have been two dominant algorithmic approaches to this problem: Greedy methods called the matching pursuit (MP) and the linear programming based approaches called the basis pursuit (BP). The aim of the current paper is to bring a fresh perspective to sparse approximation by treating it as a combinatorial optimization problem and providing an algorithm based on the powerful optimization technique semidefinite programming (SDP). In particular, we show that there is a randomized algorithm based on a semidefinite relaxation of the problem with performance guarantees depending on the coherence and the restricted isometry constant of the dictionary used. We then show a derandomization of the algorithm based on the method of conditional probabilities.
From: Ali Çivril [view email]
[v1]
Thu, 9 Feb 2017 16:51:34 UTC (12 KB)
[v2]
Mon, 22 Oct 2018 13:34:29 UTC (1 KB) (withdrawn)
[v3]
Tue, 21 Jul 2026 09:09:59 UTC (1 KB) (withdrawn)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。