Confined Orthogonal Matching Pursuit for Sparse Random Combinatorial Matrices
Orthogonal matching pursuit (OMP) is a commonly used greedy algorithm for recovering sparse signals from compressed measurements. In this paper, we introduce a variant of the OMP algorithm to reduce the complexity of reconstructing a class of $K$-sparse signals $\boldsymbol{x} \in \mathbb{R}^{n}$ from measurements $\boldsymbol{y} = \boldsymbol{A}\boldsymbol{x}$, where $\boldsymbol{A} \in \{0,1\}^{m \times n}$ is a sparse random combinatorial matrix with $d~(d \leq m/2)$ ones per column. The proposed algorithm, referred to as the confined OMP algorithm, utilizes the properties of $\boldsymbol{x}$ and $\boldsymbol{A}$ to remove much of the redundancy in the dictionary (also referred to as $\boldsymbol{A}$) and thus fewer column indices of $\boldsymbol{A}$ need to be identified. To this end, we first define a confined set $\Gamma$ with $|\Gamma| \leq n$ and then prove that the support of $\boldsymbol{x}$ is a subset of $\Gamma$ with probability 1 if the distributions of non-zero components of $\boldsymbol{x}$ satisfy a certain condition. During the process of the confined OMP algorithm, the possibly chosen column indices are strictly confined into the confined set $\Gamma$. We further develop lower bounds on the probability of exact recovery of $\boldsymbol{x}$ using OMP algorithm and confined OMP algorithm with $K$ iterations, respectively. The obtained theoretical results of confined OMP algorithm can be used to optimize the column degree $d$ of $\boldsymbol{A}$. Finally, experimental results show that the confined OMP algorithm is more efficient in reconstructing a class of sparse signals compared to the OMP algorithm.
Code (0)
등록된 구현이 없습니다.
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Orthogonal Matching Pursuit From Noisy Random Measurements: A New Analysis
Orthogonal matching pursuit (OMP) is a widely used greedy algorithm for recovering sparse vectors from linear measurements. A well-known analysis of Tropp and Gilbert shows that OMP can recover a k-sparse n-dimensional …
2k4kThe performance of orthogonal multi-matching pursuit under RIP
The orthogonal multi-matching pursuit (OMMP) is a natural extension of orthogonal matching pursuit (OMP). We denote the OMMP with the parameter $M$ as OMMP(M) where $M\geq 1$ is an integer. The main difference between OM…
Active Orthogonal Matching Pursuit for Sparse Subspace Clustering
Sparse Subspace Clustering (SSC) is a state-of-the-art method for clustering high-dimensional data points lying in a union of low-dimensional subspaces. However, while $\ell_1$ optimization-based SSC algorithms suffer fr…
ClusteringOnline Orthogonal Matching Pursuit
Greedy algorithms for feature selection are widely used for recovering sparse high-dimensional vectors in linear models. In classical procedures, the main emphasis was put on the sample complexity, with little or no cons…
feature selectionregressionRestricted Connection Orthogonal Matching Pursuit For Sparse Subspace Clustering
Sparse Subspace Clustering (SSC) is one of the most popular methods for clustering data points into their underlying subspaces. However, SSC may suffer from heavy computational burden. Orthogonal Matching Pursuit applied…
Clustering