# A Novel Coherence Reduction Method in Compressed Sensing for DOA Estimation

Authors: Jing Liu; ChongZhao Han; XiangHua Yao; Feng Lian
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

A novel method named as coherent column replacement method is proposed to reduce the coherence of a partially deterministic sensing matrix, which is comprised of highly coherent columns and random Gaussian columns. The proposed method is to replace the highly coherent columns with random Gaussian columns to obtain a new sensing matrix. The measurement vector is changed accordingly. It is proved that the original sparse signal could be reconstructed well from the newly changed measurement vector based on the new sensing matrix with large probability. This method is then extended to a more practical condition when highly coherent columns and incoherent columns are considered, for example, the direction of arrival (DOA) estimation problem in phased array radar system using compressed sensing. Numerical simulations show that the proposed method succeeds in identifying multiple targets in a sparse radar scene, where the compressed sensing method based on the original sensing matrix fails. The proposed method also obtains more precise estimation of DOA using one snapshot compared with the traditional estimation methods such as Capon, APES, and GLRT, based on hundreds of snapshots.


---

## Body

## 1. Introduction

Compressed sensing has received considerable attention recently and has been applied successfully in diverse fields, for example, image processing [1], video technology [2], wireless communication [3], and radar systems [4–10]. The central goal of compressed sensing is to capture attributes of a signal using very few measurements. In most work to date, this broader objective is exemplified by the important special case in which a K-sparse vector x∈RN (with N large) is to be reconstructed from a small number M of linear measurements with K<M<N. The two fundamental questions in compressed sensing are how to construct suitable sensing matrices Φ and how to recover x from y efficiently.In early work of compressed sensing, the entries of the sensing matrix are generated by an i.i.d Gaussian or Bernoulli process or from random Fourier ensembles [11–13]. The role of random measurement provides the worst case performance guarantees in the context of an adversarial signal/error model. Random sensing matrices are easy to construct and are 2K-RIP with high probability [13].With the application area of compressed sensing extended to wider fields, the random sensing matrix is replaced by more structured sensing matrix. Most of the recent compressed sensing work related to sensing matrix construction focuses on the construction of structured matrices which often exhibit a considerable structure [14]. This largely follows from efforts to model the way the samples are acquired in practice, which leads to sensing matrices that inherent their structure from the real world. However, most of the structured sensing matrices based on the practical acquisition equipment do not satisfy the RIP property, which guarantees the perfect reconstruction of the original sparse signal with large probability.In this paper, we are considering changing the original sensing matrix into a random Gaussian matrix or a matrix with low coherence via some software-based algorithm in the reconstruction side. Firstly, a novel method, named as coherent column replacement method, is proposed to reduce the coherence of a partially deterministic sensing matrix. The proposed method is to replace the highly coherent columns in the original sensing matrixΦ with random Gaussian columns to obtain a new sensing matrix Φ′. The measurement vector y is changed accordingly. It is proved that the original sparse signal x could be reconstructed well from the newly changed measurement vector y′ based on the new sensing matrix Φ′ with large probability.The proposed column replacement method is then extended to a more practical condition when highly coherent columns and incoherent columns are considered, for example, the direction of arrival (DOA) estimation problem in phased array radar system. The applications of compressed sensing to radar systems are investigated in [4–10]. In [4], it is demonstrated that the compressed sensing method could eliminate the need for match filter at the receiver and has the potential to reduce the required sampling rate. In the context of ground penetrating radar (GPR), [5] presents a compressed sensing based data acquisition and imaging algorithm. By exploiting the sparsity of targets in the spatial space, the proposed algorithm could generate sharper target space images with much less compressed sensing measurements than the standard back projection methods. Also the sparsity of targets in the time-frequency plane is exploited for radar in [6, 7]. In [8], compressed sensing is used to identify targets in a passive radar system. There are plenty of work concerning compressed sensing based phased array radar in recent years [9, 15, 16]. In [9], the author puts focus on the generalization of the radar signal model for compressed sensing and does not provide realizable procedures. In [15], the authors address the narrow-band source localization problem for arbitrary arrays with known geometry in the presence of arbitrary noise of unknown spatial spectral density. In [16], the authors present a source localization method based on a sparse representation of sensor measurements with an overcomplete basis composed of samples from the array manifold.Most of the present work for compressed sensing radar systems concentrates in designing the transmitted wave to implement a sensing matrixΦ with low coherence [10]. However, in phased array radar system, the steering matrix is deterministic and cannot be changed in practice. Therefore, it is required to develop a novel compressed sensing method which brings a little change to the existing hardware system of the phased array radar.In the proposed method developed for compressed sensing based phased array radar system, a hybrid system is built with a bottom subsystem and a top subsystem for reconstruction. The bottom subsystem consists of a hardware specific sensing matrixΦ, an acquired measurement vector y, and the original signal x. The original sensing matrix Φ and measurement vector y are input to the software-based top subsystem, where a new sensing matrix Φ′ and a new measurement vector y′ are generated. Since the new sensing matrix Φ′ is with low coherence, the original signal x could be reconstructed from the new measurement vector y′ perfectly with large probability. There are three key points to be aware of with this compressed sensing based approach for phased array radar system as follows. (1) There is no requirement for the transmitted signal; it could be either “incoherent” or “coherent.” (2) This approach does not use a matched filter. (3) The beamforming procedure is omitted in the proposed compressed phased array radar system.The rest of the sections are organized as follows: the proposed coherent column replacement method is introduced in Section2. In Section 3, the proposed method is extended to solve the DOA estimation problem in phased array radar system. Firstly, the signal model for DOA estimation in phased array radar system is represented in a standard compressed sensing form in Section 3.1, where the sparse radar scene is abstracted as a sparse signal. In Section 3.2, the proposed method is then used to generate a new sensing matrix with low coherence, based on which the original sparse signal could be reconstructed well with large probability. The simulation results are listed in Section 4, and the paper is summarized in Section 5.


## 2. The Proposed Coherent Column Replacement Method

Recent work related with structured sensing matrix construction tries to change the existing hardware system to generate a new sensing matrix satisfying the RIP property. In this paper, we are exploring the possibility of changing the sensing matrix and measurement vector in the reconstruction side while not changing the hardware system.It is assumed that the original sensing matrixΦ is a partially deterministic matrix which is comprised of highly coherent columns and random Gaussian columns, and this could be extended to a more practical condition when highly coherent columns and incoherent columns are considered. For the original sensing matrix Φ, its highly coherent columns and random Gaussian columns are denoted by φj, j=1,…,Nc and ψj, j=1,…,Nr, respectively. Nc is the number of highly coherent columns, and Nr is the number of random Gaussian columns with Nc+Nr=N. Without loss of generality, the highly coherent columns are put at the leftmost of the sensing matrix, while the random Gaussian columns are put next to them as Φ=[φ1,φ2,…,φNc,ψ1,ψ2,…,ψNr]. Accordingly, the signal x could be divided into two groups, x=[xc;xr]T=[xc,1,xc,2,…,xc,Nc,xr,1,xr,2,…,xr,Nr]T, where xc=[xc,1,xc,2,…,xc,Nc]T and xr=[xr,1,xr,2,…,xr,Nr]T correspond to the highly coherent columns and random Gaussian columns respectively. It is assumed that the value of each element of xc, {xc,1,xc,2,…,xc,Nc}, is chosen as either one or zero.The sensing matrixΦ is changed into a random Gaussian matrix Φ′ through replacing the highly coherent columns [φ1,φ2,…,φNc] with random Gaussian columns [φ1′,φ2′,…,φNc′]. The resulting new sensing matrix Φ′ could be represented as Φ′=[φ1′,φ2′,…,φNc′,ψ1,ψ2,…,ψNr].Lemma 1.
Given the standard model in compressed sensingy=Φx+e, where e denotes the measurement noise, and given the sensing matrix Φ′ defined above, the K-sparse signal x could be reconstructed from the new measurement vector y′=Φ′x+e perfectly with large probability. The new measurement vector y′ could be calculated via (1) provided that part of the signal x, xc=[xc,1,xc,2,…,xc,Nc]T is known:
(1)y′=y+xc,1(φ1′-φ1)+xc,2(φ2′-φ2)+⋯+xc,Nc(φNc′-φNc).Proof.
Obviously, the new sensing matrixΦ′ is a Gaussian random matrix and satisfies the RIP property. We could reconstruct x perfectly from the new measurement vector y′=Φ′x+e with large probability.
The equationy′=Φ′x+e could be expanded in columns:
(2)y′=Φ′x=xc,1φ1′+xc,2φ2′+⋯+xc,NcφNc′+xr,1ψ1+xr,2ψ2+⋯+xr,NrψNr+e.
Similarly, the equation y=Φx+e could be expanded as in
(3)y=Φx=xc,1φ1+xc,2φ2+⋯+xc,NcφNc+xr,1ψ1+xr,2ψ2+⋯+xr,NrψNr+e.
Equation (3) subtracts (2), resulting in
(4)y′-y=xc,1(φ1′-φ1)+xc,2(φ2′-φ2)+⋯+xc,Nc(φNc′-φNc).
So we can obtain the new measurement vector y′ based on the original measurement vector y and the error between the highly coherent columns and random columns:
(5)y′=y+xc,1(φ1′-φ1)+xc,2(φ2′-φ2)+⋯+xc,Nc(φNc′-φNc).
This ends the proof.However, in reality the original signalx is unknown, and it is difficult to obtain the exact value of xc (xc=[xc,1,xc,2,…,xc,Nc]T) in advance. If the number of highly coherent columns is small (e.g. Nc≤10), we could list all the configurations of xc with each element’s value chosen as one or zero. Based on each configuration, we could obtain a candidate signal using a reconstruction algorithm. The error between the true measurement and the estimate measurement based on each candidate signal is calculated and then normalized. The candidate signal with the smallest error is the one closest to the original sparse signal and is what we pursuit. The detailed procedure is listed in Algorithm 2.Algorithm 2.
The coherent column replacement method for a partially deterministic sensing matrix is as follows.(1)
The sensing matrixΦ is changed into a random Gaussian matrix Φ′ through replacing the highly coherent columns [φ1,φ2,…,φNc] with random Gaussian columns [φ1′,φ2′,…,φNc′].(2)
List all the configurations ofxc with each element’s value chosen as one or zero. The total number of configurations CN equals 2Nc. The ith configuration could be represented as λi(xc,1i,xc,2i,…,xc,Nci), i=1,…,CN and is abbreviated as λi for briefness.(3)
For theith configuration λi,   i=1,…,CN, calculate the new measurement vector y′,i via (5) and obtain a candidate signal xi using a reconstruction algorithm as
(6)xi=Reconstruct(y′,i,Φ′).(4)
For theith candidate signal xi, i=1,…,CN, calculate ERRi, which is defined as the normalized error between the true measurement and the estimate measurement based on xi,
(7)ERRi=∥y-(Φxi)∥2∥y∥2,
where ∥·∥ denotes the l2-norm.(5)
Find the smallest one in{ERRi,i=1,…,CN} and define it as ERRmin. The candidate signal corresponding to ERRmin is what we pursuit and is defined as xestimate.In the above algorithm, “Reconstruct” in (6) refers to any available reconstruction algorithm and the basis pursuit denoising (BPDN) method [14] is chosen as the reconstruction algorithm here.


## 3. Compressed Sensing Based DOA Estimation in Phased Array Radar System

In this section, the proposed column replacement method is extended to solve the DOA estimation problem in phased array radar system. Firstly, the signal model for DOA estimation in phased array radar system is represented in a standard compressed sensing form in Section3.1, where the sparse radar scene is abstracted as a sparse signal. In Section 3.2, the proposed method is then used to generate a new sensing matrix with low coherence, based on which the original sparse signal could be reconstructed well with large probability.


### 3.1. Signal Model for DOA Estimation and Sparse Representation

Assume a phased array radar system consisting of half-wavelength spaced uniform linear arrays (ULA). Targets may appear at directions represented by DOA angles. The task of signal processing is to estimate the directions to the targets and the corresponding complex amplitudes (DOA estimation, see [17]). We assume that the other parameters like range and Doppler frequency have been isolated before by appropriate processing.The ULA of the phased array radar system consists ofM antennas, which are used to emit the transmitted signal s(t). The M×1 received complex vector of array observations is defined as F(t)=[f1(t),…,fM(t)]T. Assuming a hypothetical target located at a DOA angle of θ in the far field, the received complex vector of array observations can be written as
(8)F(t)=β(θ)s(t)a(θ)+E(t),
where β(θ) is the reflection coefficient of the hypothetical target, and E(t) is a M×1 complex Gaussian noise vector. a(θ) is the M×1 steering vector, which is defined as
(9)a(θ)=[1ej(2πdsinθ/λ),…,ej(M-1)(2πdsinθ/λ)]T,
where d is the distance between the elements of the arrays, and λ denotes wavelength.AssumingD targets are observed with reflection coefficients {βi}i=1D and DOA angles {θi}i=1D, the M×1 received complex vector of array observations can be written as
(10)FM(t)=∑i=1Dβ(θi)s(t)a(θi)+EM(t),
where EM(t) is a M×1 complex Gaussian noise vector. Equation (10) could be rewritten as
(11)FM(t)=A(θ)S(t,θ)+EM(t),
where A(θ)=[a(θ1),a(θ2),…,a(θD)] is a M×D steering matrix, and S(t,θ)=s(t)[β(θ1),β(θ2),…,β(θD)]T denotes a D×1 reflection vector.Since the radar scene is generally in practice sparse, compressed sensing is a valid candidate for estimating the DOA angles for multiple targets. To do so, the DOA angle plane is divided intoN fine grids, each cell generally with the same size Δθ. The ith grid represents the DOA angle of θ0+(i-1)Δθ, where θ0 is the initial angle of the DOA plane. Each cell has a unique mathematical representation as well as physical explanation: for example, if a target’s DOA angle occupies the ith grid, its contribution could be uniquely written as s(t)β(θ0+(i-1)Δθ)a→(θ0+(i-1)Δθ). Now, the DOA estimation problem is recast as the search for the grid cells in which the targets lie.As the system has no knowledge of the numbers and locations of the targets, the information of all the grids in the DOA plane should be considered. Therefore, the steering matrix and reflection vector in (11) are extended to obtain the M×N extended steering matrix Φ and the N×1 extended reflection vector x, which are defined as Φ=[a(θ0),a(θ0+Δθ),…,a(θ0+(i-1)Δθ)a(θ0+(N-1)Δθ)] and x=s(t)[β(θ0)β(θ0+Δθ),…,β(θ0+(i-1)Δθ)β(θ0+(N-1)Δθ)]T. Since small numbers of grids are occupied by the targets, x is a sparse vector with the ith element defined as x(i)=s(t)β(θ0+(i-1)Δθ) if the ith grid is occupied by the target; otherwise, x(i)=0. As a result, the M×1 received complex vector of array observations y could be written as follows:
(12)y=Φx+e,
where e is a M×1 complex Gaussian noise vector. Though in (12) the radar vectors and matrices are complex valued in contrary to the original compressed sensing environment, it is easy to transfer it to real variables according to [9, 18].Discussion. In [10, 19], it is assumed that the discretized step is small enough so that each target falls on some specific grid point. However, no matter how finely the parameter space is gridded, the sources may not lie in the center of the grid cells, and consequently there is a mismatch between the assumed and the actual bases for sparsity. The sensitivity of compressed sensing to mismatch between the assumed and the actual sparsity bases is studied in [20]. The effect of basis mismatch is analyzed on the best k-term approximation error, and some achievable bounds for the l1 error of the best k-term approximation are provided. The readers can refer to [20] for a detailed analysis on the influence of the griding operations on the estimation performance.


### 3.2. DOA Estimation Based on the Column Replacement Method

The proposed column replacement method is then extended to solve the DOA estimation problem in phased array radar system where the sensing matrix is comprised of highly coherent columns and incoherent columns. In order to distinguish the highly coherent columns from the incoherent columns, the coherence of the sensing matrix is adopted, which is defined in [21, 22] as follows.Definition 3.
For the sensing matrixΦ, its coherence is defined as the largest absolute and normalized inner product between different columns in Φ. Formally, this reads
(13)μ{Φ}=max1≤i,j≤N,i≠j|ΦiTΦj|∥Φi∥·∥Φj∥
The coherence provides a measure of the worst similarity between the sensing matrix columns.
A different way to understand the coherence is by considering the Gram matrixG which is defined as
(14)G=ΦT~Φ~,
where ΦT~ is the normalized sensing matrix obtained from the original sensing matrix with each column normalized. The off-diagonal entries in G are the inner products that appear in (13). The coherence is the off-diagonal entry gi,j with the largest magnitude.
In the proposed method, the Gram matrixG is firstly built via (14), and a threshold T is then set properly to distinguish the highly coherent columns from the incoherent columns as follows. For each off-diagonal entry {gi,j,i=1,…,N,j=1,…,N}, if gi,j is larger than T, the columns i and j are added to the set of highly coherent columns. The remaining columns that do not belong to the set of highly coherent columns form the set of incoherent columns.
The set of highly coherent columns and the set of incoherent columns are denoted byαj, j=1,…,Nhc and βj, j=1,…,Nic, respectively. Nhc is the number of highly coherent columns, and Nic is the number of incoherent columns with Nhc+Nic=N. Without loss of generality, the highly coherent columns are put at the leftmost of the sensing matrix, while the incoherent columns are put next to them as Φ=[α1,α2,…,αNhc,β1,β2,…,βNic]. Accordingly, the signal x could be divided into two groups, x=[xhc;xic]T=[xhc,1,xhc,2,…,xhc,Nhc,xic,1,xic,2,…,xic,Nic]T, where xhc=[xhc,1,xhc,2,…,xhc,Nhc]T and xic=[xic,1,xic,2,…,xic,Nic]T correspond to the highly coherent columns and incoherent columns respectively. It is assumed that the value of each element of xhc, {xhc,1,xhc,2,…,xhc,Nhc} is chosen as either one or zero.
The sensing matrixΦ is changed into a new matrix Φ′ through replacing the highly coherent columns [α1,α2,…,αNhc] with random Gaussian columns [α1′,α2′,…,αNhc′]. The resulted new sensing matrix Φ′ could be represented as Φ′=[α1′,α2′,…,αNhc′,β1,β2,…,βNic].Theorem 4 (see [23]).
Letx be a K-sparse signal, and write y=Φx+e, where e~N(0;σ2I). Suppose that
(15)K<13μ(Φ),
and consider the BPDN optimization problem (16) with λ=16σ2logM:
(16)x^=arg minx∈RN∥x∥1+λ∥y-Φx∥2.
Then, with probability on the order of 1-1/M2, the solution x^ of (16) is unique, and its error is bounded by
(17)∥x-x^∥2≤CσKlogM,
and its support is a subset of the true K-element support of x.Lemma 5.
Given the standard model in compressed sensingy=Φx+e and given the sensing matrix Φ′ defined above, the K-sparse signal x could be reconstructed from the new measurement vector y′=Φ′x+e perfectly using the BPDN optimization method with probability on the order of 1-1/M2. The new measurement vector y′ could be calculated via (18) provided that part of the signal x, xhc=[xhc,1,xhc,2,…,xhc,Nhc]T is known:
(18)y′=y+xhc,1(α1′-α1)+xhc,2(α2′-α2)+⋯+xhc,Nhc(αNhc′-αNhc).Proof.
The thresholdT is set to distinguish the highly coherent columns from the incoherent columns. In theory, the threshold T could be designed as small as possible to obtain a very small coherence μ(Φ). As a consequence, the new sensing matrix Φ′ satisfies (15) properly with set threshold T. We could reconstruct x perfectly from the new measurement vector y′=Φ′x+e using the BPDN optimization method with probability on the order of 1-1/M2 according to Theorem 4. The deviation of (18) is similar to that of (1). This ends the proof.However, in reality the original signalx is unknown, and it is difficult to obtain the exact value of xhc (xhc=[xhc,1,xhc,2,…,xhc,Nhc]T) in advance. If the number of highly coherent columns is small (e.g., Nhc≤10), we could list all the configurations of xhc with each element’s value chosen as one or zero. Based on each configuration, we could obtain a candidate signal using a reconstruction algorithm. The error between the true measurement and the estimate measurement based on each candidate signal is calculated and then normalized. The candidate signal with the smallest error is the one closest to the original sparse signal and is what we pursuit. The detailed procedure is listed in Algorithm 6.Algorithm 6.
The coherent column replacement method for a deterministic sensing matrix is as follows.(1)
The Gram matrixG is firstly built via (14), and a threshold T is then set properly to distinguish the highly coherent columns from the incoherent columns as follows. For each off-diagonal entry {gi,j,i=1,…,N,j=1,…,N}, if gi,j is larger than T, the columns i and j are added to the set of highly coherent columns. The remaining columns that do not belong to the set of highly coherent columns form the set of incoherent columns.(2)
The sensing matrixΦ is changed into a new sensing matrix Φ′ through replacing the highly coherent columns [α1,α2,…,αNhc] with random Gaussian columns [α1′,α2′,…,αNhc′].
Steps (3)–(6) are the same as steps (2)–( 5) in Algorithm2.


## 3.1. Signal Model for DOA Estimation and Sparse Representation

Assume a phased array radar system consisting of half-wavelength spaced uniform linear arrays (ULA). Targets may appear at directions represented by DOA angles. The task of signal processing is to estimate the directions to the targets and the corresponding complex amplitudes (DOA estimation, see [17]). We assume that the other parameters like range and Doppler frequency have been isolated before by appropriate processing.The ULA of the phased array radar system consists ofM antennas, which are used to emit the transmitted signal s(t). The M×1 received complex vector of array observations is defined as F(t)=[f1(t),…,fM(t)]T. Assuming a hypothetical target located at a DOA angle of θ in the far field, the received complex vector of array observations can be written as
(8)F(t)=β(θ)s(t)a(θ)+E(t),
where β(θ) is the reflection coefficient of the hypothetical target, and E(t) is a M×1 complex Gaussian noise vector. a(θ) is the M×1 steering vector, which is defined as
(9)a(θ)=[1ej(2πdsinθ/λ),…,ej(M-1)(2πdsinθ/λ)]T,
where d is the distance between the elements of the arrays, and λ denotes wavelength.AssumingD targets are observed with reflection coefficients {βi}i=1D and DOA angles {θi}i=1D, the M×1 received complex vector of array observations can be written as
(10)FM(t)=∑i=1Dβ(θi)s(t)a(θi)+EM(t),
where EM(t) is a M×1 complex Gaussian noise vector. Equation (10) could be rewritten as
(11)FM(t)=A(θ)S(t,θ)+EM(t),
where A(θ)=[a(θ1),a(θ2),…,a(θD)] is a M×D steering matrix, and S(t,θ)=s(t)[β(θ1),β(θ2),…,β(θD)]T denotes a D×1 reflection vector.Since the radar scene is generally in practice sparse, compressed sensing is a valid candidate for estimating the DOA angles for multiple targets. To do so, the DOA angle plane is divided intoN fine grids, each cell generally with the same size Δθ. The ith grid represents the DOA angle of θ0+(i-1)Δθ, where θ0 is the initial angle of the DOA plane. Each cell has a unique mathematical representation as well as physical explanation: for example, if a target’s DOA angle occupies the ith grid, its contribution could be uniquely written as s(t)β(θ0+(i-1)Δθ)a→(θ0+(i-1)Δθ). Now, the DOA estimation problem is recast as the search for the grid cells in which the targets lie.As the system has no knowledge of the numbers and locations of the targets, the information of all the grids in the DOA plane should be considered. Therefore, the steering matrix and reflection vector in (11) are extended to obtain the M×N extended steering matrix Φ and the N×1 extended reflection vector x, which are defined as Φ=[a(θ0),a(θ0+Δθ),…,a(θ0+(i-1)Δθ)a(θ0+(N-1)Δθ)] and x=s(t)[β(θ0)β(θ0+Δθ),…,β(θ0+(i-1)Δθ)β(θ0+(N-1)Δθ)]T. Since small numbers of grids are occupied by the targets, x is a sparse vector with the ith element defined as x(i)=s(t)β(θ0+(i-1)Δθ) if the ith grid is occupied by the target; otherwise, x(i)=0. As a result, the M×1 received complex vector of array observations y could be written as follows:
(12)y=Φx+e,
where e is a M×1 complex Gaussian noise vector. Though in (12) the radar vectors and matrices are complex valued in contrary to the original compressed sensing environment, it is easy to transfer it to real variables according to [9, 18].Discussion. In [10, 19], it is assumed that the discretized step is small enough so that each target falls on some specific grid point. However, no matter how finely the parameter space is gridded, the sources may not lie in the center of the grid cells, and consequently there is a mismatch between the assumed and the actual bases for sparsity. The sensitivity of compressed sensing to mismatch between the assumed and the actual sparsity bases is studied in [20]. The effect of basis mismatch is analyzed on the best k-term approximation error, and some achievable bounds for the l1 error of the best k-term approximation are provided. The readers can refer to [20] for a detailed analysis on the influence of the griding operations on the estimation performance.


## 3.2. DOA Estimation Based on the Column Replacement Method

The proposed column replacement method is then extended to solve the DOA estimation problem in phased array radar system where the sensing matrix is comprised of highly coherent columns and incoherent columns. In order to distinguish the highly coherent columns from the incoherent columns, the coherence of the sensing matrix is adopted, which is defined in [21, 22] as follows.Definition 3.
For the sensing matrixΦ, its coherence is defined as the largest absolute and normalized inner product between different columns in Φ. Formally, this reads
(13)μ{Φ}=max1≤i,j≤N,i≠j|ΦiTΦj|∥Φi∥·∥Φj∥
The coherence provides a measure of the worst similarity between the sensing matrix columns.
A different way to understand the coherence is by considering the Gram matrixG which is defined as
(14)G=ΦT~Φ~,
where ΦT~ is the normalized sensing matrix obtained from the original sensing matrix with each column normalized. The off-diagonal entries in G are the inner products that appear in (13). The coherence is the off-diagonal entry gi,j with the largest magnitude.
In the proposed method, the Gram matrixG is firstly built via (14), and a threshold T is then set properly to distinguish the highly coherent columns from the incoherent columns as follows. For each off-diagonal entry {gi,j,i=1,…,N,j=1,…,N}, if gi,j is larger than T, the columns i and j are added to the set of highly coherent columns. The remaining columns that do not belong to the set of highly coherent columns form the set of incoherent columns.
The set of highly coherent columns and the set of incoherent columns are denoted byαj, j=1,…,Nhc and βj, j=1,…,Nic, respectively. Nhc is the number of highly coherent columns, and Nic is the number of incoherent columns with Nhc+Nic=N. Without loss of generality, the highly coherent columns are put at the leftmost of the sensing matrix, while the incoherent columns are put next to them as Φ=[α1,α2,…,αNhc,β1,β2,…,βNic]. Accordingly, the signal x could be divided into two groups, x=[xhc;xic]T=[xhc,1,xhc,2,…,xhc,Nhc,xic,1,xic,2,…,xic,Nic]T, where xhc=[xhc,1,xhc,2,…,xhc,Nhc]T and xic=[xic,1,xic,2,…,xic,Nic]T correspond to the highly coherent columns and incoherent columns respectively. It is assumed that the value of each element of xhc, {xhc,1,xhc,2,…,xhc,Nhc} is chosen as either one or zero.
The sensing matrixΦ is changed into a new matrix Φ′ through replacing the highly coherent columns [α1,α2,…,αNhc] with random Gaussian columns [α1′,α2′,…,αNhc′]. The resulted new sensing matrix Φ′ could be represented as Φ′=[α1′,α2′,…,αNhc′,β1,β2,…,βNic].Theorem 4 (see [23]).
Letx be a K-sparse signal, and write y=Φx+e, where e~N(0;σ2I). Suppose that
(15)K<13μ(Φ),
and consider the BPDN optimization problem (16) with λ=16σ2logM:
(16)x^=arg minx∈RN∥x∥1+λ∥y-Φx∥2.
Then, with probability on the order of 1-1/M2, the solution x^ of (16) is unique, and its error is bounded by
(17)∥x-x^∥2≤CσKlogM,
and its support is a subset of the true K-element support of x.Lemma 5.
Given the standard model in compressed sensingy=Φx+e and given the sensing matrix Φ′ defined above, the K-sparse signal x could be reconstructed from the new measurement vector y′=Φ′x+e perfectly using the BPDN optimization method with probability on the order of 1-1/M2. The new measurement vector y′ could be calculated via (18) provided that part of the signal x, xhc=[xhc,1,xhc,2,…,xhc,Nhc]T is known:
(18)y′=y+xhc,1(α1′-α1)+xhc,2(α2′-α2)+⋯+xhc,Nhc(αNhc′-αNhc).Proof.
The thresholdT is set to distinguish the highly coherent columns from the incoherent columns. In theory, the threshold T could be designed as small as possible to obtain a very small coherence μ(Φ). As a consequence, the new sensing matrix Φ′ satisfies (15) properly with set threshold T. We could reconstruct x perfectly from the new measurement vector y′=Φ′x+e using the BPDN optimization method with probability on the order of 1-1/M2 according to Theorem 4. The deviation of (18) is similar to that of (1). This ends the proof.However, in reality the original signalx is unknown, and it is difficult to obtain the exact value of xhc (xhc=[xhc,1,xhc,2,…,xhc,Nhc]T) in advance. If the number of highly coherent columns is small (e.g., Nhc≤10), we could list all the configurations of xhc with each element’s value chosen as one or zero. Based on each configuration, we could obtain a candidate signal using a reconstruction algorithm. The error between the true measurement and the estimate measurement based on each candidate signal is calculated and then normalized. The candidate signal with the smallest error is the one closest to the original sparse signal and is what we pursuit. The detailed procedure is listed in Algorithm 6.Algorithm 6.
The coherent column replacement method for a deterministic sensing matrix is as follows.(1)
The Gram matrixG is firstly built via (14), and a threshold T is then set properly to distinguish the highly coherent columns from the incoherent columns as follows. For each off-diagonal entry {gi,j,i=1,…,N,j=1,…,N}, if gi,j is larger than T, the columns i and j are added to the set of highly coherent columns. The remaining columns that do not belong to the set of highly coherent columns form the set of incoherent columns.(2)
The sensing matrixΦ is changed into a new sensing matrix Φ′ through replacing the highly coherent columns [α1,α2,…,αNhc] with random Gaussian columns [α1′,α2′,…,αNhc′].
Steps (3)–(6) are the same as steps (2)–( 5) in Algorithm2.


## 4. Simulation Results and Analysis

In this section, a simple example is firstly carried out to verify the performance of the proposed column replacement algorithm for a partially deterministic sensing matrix. The proposed method is then extended to cope with the DOA estimation problem in phased array radar system.


### 4.1. A Simple Example

In this section, a simple example is used to evaluate the performance of the proposed algorithm. The original sensing matrixΦ is a 20×30 matrix with 5(Nc) highly coherent columns, which are put at the leftmost of it, and 25(Nr) random Gaussian columns. The original signal x is shown in Figure 1, which shows that its nonzero entries are in indexes {1,3,5,11,17,20,27}. Since the highly coherent columns are put at the leftmost of Φ, the true value of xc is xc={xc,1=1,xc,2=0,xc,3=1,xc,4=0,xc,5=1} (abbreviated as 10101). In the proposed method, each element of xc, {xc,1,xc,2,…,xc,5} is chosen as one or zero, resulting in totally 25=32 configurations as {00000,00001,00010,…,11111}. The reconstruction error obtained based on each configuration in one trial is shown in Figure 2, which shows that the configuration number with the smallest reconstruction error is 21 (10101 in binary format). This matches the true xc exactly. The whole reconstructed signal corresponding to configuration 21 is shown in Figure 3. Moreover, five hundred Monte Carlo simulations are carried out, and the average reconstruction error is shown in Figure 4, which shows that the configuration 21 is with the smallest average reconstruction error 0.06868.Figure 1
The original signalx.Figure 2
Reconstruction error based on configurations ofxc in one trial.Figure 3
Reconstructed signal corresponding to the configuration with the smallest reconstruction error.Figure 4
Average reconstruction error based on configurations ofxc.


### 4.2. DOA Estimation Based on the Proposed Column Replacement Method

In this section, a synthetic example about DOA estimation based on the phased array radar system is provided. A hybrid system is built which consists of a bottom subsystem and a top subsystem. The bottom subsystem is built based on the specific hardware structure of the phased array system, which consists of half-wavelength spaced uniform linear arrays (ULA). The number of transmit/receive antennas is20. The antennas transmit independent orthogonal quadrature phase shift keyed (QPSK) waveforms, and the carrier frequency is 8.62GHz. The SNR of the measurement noise is set to a fixed value (20 dB). The range of the DOA plane is [0°,90°], which is divided into 30 cells with the initial angle (θ0) and angle interval (Δθ) equaling 0° and 3°, respectively. A maximum of L=512 snapshots are considered at the receive node. Targets may appear at directions represented by DOA angles. The task of signal processing is to estimate the directions to the targets and the corresponding complex amplitudes (DOA estimation; see [17]).In the proposed method, the Gram matrixG of the original sensing matrix Φ is built via (14). In the next, we will set the threshold T to distinguish the highly coherent columns from the incoherent columns. In theory, the threshold T is designed as small as possible to obtain a very small coherence μ(Φ), which guarantees the perfect reconstruction of the K-sparse signal x. However, small T will result in a large number of highly coherent columns, leading to a huge number of configurations of xhc. This will increase the computing time dramatically. While the restrict selection of T is true from a worst-case standpoint, it turns out that the coherence as defined previously does not do justice to the actual behavior of sparse representations and pursuit algorithms’ performance. Thus, if we relax our expectations and allow a small fraction of failed reconstructions, then values substantially beyond the above bound are still leading to successful compressed sensing [24]. In this simulation example, the threshold T is set as 0.6, resulting in 10 highly coherent columns and 20 incoherent columns.A new sensing matrixΦ′ is then generated, based on which a new Gram matrix G′ is built. Figures 5 and 6 present the histograms of the absolute off-diagonal entries of G and G′ respectively. As can be seen, there is a shift towards the origin of the histogram after using the proposed method. The tail representing the higher values in Figure 5 disappears in Figure 6. Therefore the coherence of the new sensing matrix Φ′ is far less than that of the original sensing matrix Φ.Figure 5
Histogram of the absolute off-diagonal entries ofG based on the original sensing matrix.Figure 6
Histogram of the absolute off-diagonal entries ofG′ based on the new sensing matrix, using a fixed threshold t=0.6.Firstly, the performance of the proposed column replacement method is compared to the compressed sensing method using the original sensing matrix (abbreviated as standard compressed sensing) and other three commonly used estimation methods, the Capon, APES, and GLRT method, in one trial. Figure7 shows the original scene, the modulus of the reflection coefficients βk, as functions of the DOA. Figures 8, 9, 10, 11, and 12 correspond to the DOA estimates obtained via the standard compressed sensing method, the proposed method, Capon, APES, and GLRT, respectively. The proposed method and the standard compressed sensing method use one snapshot only, and the other three methods use 512 snapshots each. One can see that the presence of the four targets is clearly evident via the proposed method (Figure 9), while the standard compressed sensing method fails in identifying the targets (Figure 8). Secondly, five hundred Monte Carlo simulations are carried out, and in each trial four targets are located randomly within the DOA range of [0°,90°], and the corresponding reflection coefficients are set as {βk=1,k=1,…,4}. The performance of the proposed method is compared to the standard compressed sensing method via the average reconstruction error and the average root mean square error (RMSE) [25] of the estimated DOA angles of all four targets. The results in Table 1 show that the proposed method is with less reconstruction error and RMSE. This shows that the proposed method outperforms the standard compressed sensing with more accurate estimated DOA angles.Table 1
Performance comparison.
Average reconstruction error
Average RMSEof DOA angles (degree)
Standard compressed sensing
0.64
2.5
The proposed algorithm
0.04
0.01Figure 7
The original scene.Figure 8
DOA estimation using the standard compressed sensing method.Figure 9
DOA estimation using the proposed coherent column replacement method.Figure 10
DOA estimation using Capon.Figure 11
DOA estimation using APES.Figure 12
DOA estimation using GLRT.


## 4.1. A Simple Example

In this section, a simple example is used to evaluate the performance of the proposed algorithm. The original sensing matrixΦ is a 20×30 matrix with 5(Nc) highly coherent columns, which are put at the leftmost of it, and 25(Nr) random Gaussian columns. The original signal x is shown in Figure 1, which shows that its nonzero entries are in indexes {1,3,5,11,17,20,27}. Since the highly coherent columns are put at the leftmost of Φ, the true value of xc is xc={xc,1=1,xc,2=0,xc,3=1,xc,4=0,xc,5=1} (abbreviated as 10101). In the proposed method, each element of xc, {xc,1,xc,2,…,xc,5} is chosen as one or zero, resulting in totally 25=32 configurations as {00000,00001,00010,…,11111}. The reconstruction error obtained based on each configuration in one trial is shown in Figure 2, which shows that the configuration number with the smallest reconstruction error is 21 (10101 in binary format). This matches the true xc exactly. The whole reconstructed signal corresponding to configuration 21 is shown in Figure 3. Moreover, five hundred Monte Carlo simulations are carried out, and the average reconstruction error is shown in Figure 4, which shows that the configuration 21 is with the smallest average reconstruction error 0.06868.Figure 1
The original signalx.Figure 2
Reconstruction error based on configurations ofxc in one trial.Figure 3
Reconstructed signal corresponding to the configuration with the smallest reconstruction error.Figure 4
Average reconstruction error based on configurations ofxc.


## 4.2. DOA Estimation Based on the Proposed Column Replacement Method

In this section, a synthetic example about DOA estimation based on the phased array radar system is provided. A hybrid system is built which consists of a bottom subsystem and a top subsystem. The bottom subsystem is built based on the specific hardware structure of the phased array system, which consists of half-wavelength spaced uniform linear arrays (ULA). The number of transmit/receive antennas is20. The antennas transmit independent orthogonal quadrature phase shift keyed (QPSK) waveforms, and the carrier frequency is 8.62GHz. The SNR of the measurement noise is set to a fixed value (20 dB). The range of the DOA plane is [0°,90°], which is divided into 30 cells with the initial angle (θ0) and angle interval (Δθ) equaling 0° and 3°, respectively. A maximum of L=512 snapshots are considered at the receive node. Targets may appear at directions represented by DOA angles. The task of signal processing is to estimate the directions to the targets and the corresponding complex amplitudes (DOA estimation; see [17]).In the proposed method, the Gram matrixG of the original sensing matrix Φ is built via (14). In the next, we will set the threshold T to distinguish the highly coherent columns from the incoherent columns. In theory, the threshold T is designed as small as possible to obtain a very small coherence μ(Φ), which guarantees the perfect reconstruction of the K-sparse signal x. However, small T will result in a large number of highly coherent columns, leading to a huge number of configurations of xhc. This will increase the computing time dramatically. While the restrict selection of T is true from a worst-case standpoint, it turns out that the coherence as defined previously does not do justice to the actual behavior of sparse representations and pursuit algorithms’ performance. Thus, if we relax our expectations and allow a small fraction of failed reconstructions, then values substantially beyond the above bound are still leading to successful compressed sensing [24]. In this simulation example, the threshold T is set as 0.6, resulting in 10 highly coherent columns and 20 incoherent columns.A new sensing matrixΦ′ is then generated, based on which a new Gram matrix G′ is built. Figures 5 and 6 present the histograms of the absolute off-diagonal entries of G and G′ respectively. As can be seen, there is a shift towards the origin of the histogram after using the proposed method. The tail representing the higher values in Figure 5 disappears in Figure 6. Therefore the coherence of the new sensing matrix Φ′ is far less than that of the original sensing matrix Φ.Figure 5
Histogram of the absolute off-diagonal entries ofG based on the original sensing matrix.Figure 6
Histogram of the absolute off-diagonal entries ofG′ based on the new sensing matrix, using a fixed threshold t=0.6.Firstly, the performance of the proposed column replacement method is compared to the compressed sensing method using the original sensing matrix (abbreviated as standard compressed sensing) and other three commonly used estimation methods, the Capon, APES, and GLRT method, in one trial. Figure7 shows the original scene, the modulus of the reflection coefficients βk, as functions of the DOA. Figures 8, 9, 10, 11, and 12 correspond to the DOA estimates obtained via the standard compressed sensing method, the proposed method, Capon, APES, and GLRT, respectively. The proposed method and the standard compressed sensing method use one snapshot only, and the other three methods use 512 snapshots each. One can see that the presence of the four targets is clearly evident via the proposed method (Figure 9), while the standard compressed sensing method fails in identifying the targets (Figure 8). Secondly, five hundred Monte Carlo simulations are carried out, and in each trial four targets are located randomly within the DOA range of [0°,90°], and the corresponding reflection coefficients are set as {βk=1,k=1,…,4}. The performance of the proposed method is compared to the standard compressed sensing method via the average reconstruction error and the average root mean square error (RMSE) [25] of the estimated DOA angles of all four targets. The results in Table 1 show that the proposed method is with less reconstruction error and RMSE. This shows that the proposed method outperforms the standard compressed sensing with more accurate estimated DOA angles.Table 1
Performance comparison.
Average reconstruction error
Average RMSEof DOA angles (degree)
Standard compressed sensing
0.64
2.5
The proposed algorithm
0.04
0.01Figure 7
The original scene.Figure 8
DOA estimation using the standard compressed sensing method.Figure 9
DOA estimation using the proposed coherent column replacement method.Figure 10
DOA estimation using Capon.Figure 11
DOA estimation using APES.Figure 12
DOA estimation using GLRT.


## 5. Conclusion

In this paper, the coherent column replacement method is proposed to reduce the coherence of a partially deterministic sensing matrix, which is comprised of highly coherent columns and random Gaussian columns. The proposed method is then extended to a more practical condition when highly coherent columns and incoherent columns are considered, for example, the direction of arrival (DOA) estimation problem in phased array radar system using compressed sensing. Numerical simulations show that the proposed method obtains more precise estimation of DOA using one snapshot compared with the traditional estimation methods such as Capon, APES, and GLRT, based on hundreds of snapshots.



---

*Source: 548979-2013-05-29.xml*