Sparsity-based estimators

API references

class doatools.estimation.sparse.SparseCovarianceMatching(array, wavelength, search_grid, noise_known=False, formulation='penalizedl1', **kwargs)[source]

Bases: doatools.estimation.core.SpectrumBasedEstimatorBase

Creates a source location estimator based on matching the sparse representation of the covariance matrix.

The sources are assumed to be uncorrelated. Take 1D far-field sources as an example. After discretizing the range of source locations into a fine grid of \(G\) points, \(\mathbf{\theta} = [\theta_1, \ldots, \theta_G]^T\), the vectorized covariance matrix can be expressed as

\[\begin{split}\mathbf{r} = \begin{bmatrix} \mathbf{A}^*(\mathbf{\theta}) \odot \mathbf{A}(\mathbf{\theta}) & \mathrm{vec}(\mathbf{I}) \end{bmatrix} \begin{bmatrix} \mathbf{p} \\ \sigma^2 \end{bmatrix}\end{split}\]

where \(\mathbf{A}\) is the steering matrix of the discretized source locations, \(\mathbf{p} \in \mathbb{R}_+^G\) is a sparse vector of the source powers, and \(\sigma^2\) is the noise variance. If all sources are located on the grid, \(p_k\) should be non-zero if there is a source located at \(\theta_k\) and zero otherwise.

Let \(\mathbf{\Phi} = \lbrack \mathbf{A}^* \odot \mathbf{A}, \mathrm{vec}(\mathbf{I}) \rbrack\), and \(\mathbf{x} = \lbrack \mathbf{p}^T, \sigma^2 \rbrack^T\). We have \(\mathbf{r} = \mathbf{\Phi} \mathbf{x}\), where \(\mathbf{x}\) is sparse. We call this expression the sparse representation of the covariance matrix. Given the estimate of \(\mathbf{r}\), \(\hat{\mathbf{r}}\), we can formulate a sparse recovery problem to recovery the sparse vector \(\mathbf{x}\), and then recover the source locations.

Parameters:
  • array (ArrayDesign) – Array design.
  • wavelength (float) – Wavelength of the carrier wave.
  • search_grid (SearchGrid) – The search grid used to locate the sources.
  • formulation (str) – 'penalizedl1', 'constrainedl1', or 'constrainedl2'.
  • **kwargs – Other keyword arguments supported by SpectrumBasedEstimatorBase.

References

[1] J. Yin and T. Chen, “Direction-of-Arrival Estimation Using a Sparse Representation of Array Covariance Vectors,” IEEE Transactions on Signal Processing, vol. 59, no. 9, pp. 4489–4493, Sep. 2011.

[2] Y. D. Zhang, M. G. Amin, and B. Himed, “Sparsity-based DOA estimation using co-prime arrays,” in 2013 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2013, pp. 3967-3971.

[3] Z. Tan and A. Nehorai, “Sparse direction of arrival estimation using co-prime arrays with off-grid targets,” IEEE Signal Processing Letters, vol. 21, no. 1, pp. 26-29, Jan. 2014.

estimate(R, k, l, sigma=None, solver_options={}, **kwargs)[source]

Estimates the source locations from the given covariance matrix.

Parameters:
  • R (ndarray) – Covariance matrix input. The size of R must match that of the array design used when creating this estimator.
  • k (int) – Expected number of sources.
  • l (float) –

    The regularization parameter. The meaning of this parameter depends on the formulation:

    • 'penalizedl1': regularization parameter of the l1 penalty term. Larger values of l usually leads to more sparse solutions, at the cost of increased biases.
    • 'constrainedl1': upper bound of the l1 norm of the signal vector. Smaller values of l usually leads to more sparse solutions, at the cost of increased biases.
    • 'constrainedl2': upper bound of the l2 norm of the residual. Smaller values of l usually leads to better reconstruction results. However the optimization problem will become infeasible if l is too small.

    See L1RegularizedLeastSquaresProblem for more details.

  • solver_options (dict) – A dictionary of additional keyword arguments to be passed to the optimizer. For instance, you can specify the solver or set the verbosity.
  • return_spectrum (bool) – Set to True to also output the spectrum for visualization. Default value if False.
Returns:

A tuple with the following elements.

  • resolved (bool): True is the solver successfully obtained the sparse solution and the peak finder successfully identified the desired number of peaks. This flag does not guarantee that the estimated source locations are correct. The estimated source locations may be completely wrong! If resolved is False, both estimates and spectrum will be None.
  • estimates (SourcePlacement): A SourcePlacement instance of the same type as the one used in the search grid, represeting the estimated source locations. Will be None if resolved is False.
  • spectrum (ndarray): An numpy array of the same shape of the specified search grid, consisting of values evaluated at the grid points. Only present if return_spectrum is True.
class doatools.estimation.sparse.GroupSparseEstimator(array, wavelength, search_grid, n_snapshots, **kwargs)[source]

Bases: doatools.estimation.core.SpectrumBasedEstimatorBase

Creates a group-sparsity based estimator.

The group-sparsity based estimator considers the following mulitple measurement vector (MMV) model:

\[\mathbf{Y} = \mathbf{A} \mathbf{X} + \mathbf{N},\]

where each column of \(\mathbf{Y}\) represents a single snapshot vector, each column of \(\mathbf{X}\) represents a single source signal vector, each column of \(\mathbf{N}\) represents a single noise vector.

Similar to SparseCovarianceMatching, we discretize the range of source locations into a fine grid, and \(\mathbf{A}\) is the steering matrix of the discretized source locations. If we can find out the non-zero rows of \(\mathbf{X}\), we can then recover the source locations.

The group-sparsity based estimator solves the following mixed-norm optimization problem:

\[\min_{\mathbf{X}} \frac{1}{2}\| \mathbf{A}\mathbf{X} - \mathbf{Y} \|_2 + \lambda \| \mathbf{X} \|_{2,1},\]

where \(\lambda\) is the regularization parameter, and

\[\| \mathbf{X} \|_{2,1} =\sum_{i} \left(\sum_{j} |X_{ij}|^2\right)^{\frac{1}{2}}.\]

After recovering \(\mathbf{X}\), the \(l_2\) norms of the rows of \(\mathbf{X}\) forms a pseudo spectrum. We can then find the source locations by identifying the largest peaks.

Parameters:
  • array (ArrayDesign) – Array design.
  • wavelength (float) – Wavelength of the carrier wave.
  • search_grid (SearchGrid) – The search grid used to locate the sources.
  • n_snapshots (int) – Number of snapshots used.
  • **kwargs – Other keyword arguments supported by SpectrumBasedEstimatorBase.

References

[1] D. Malioutov, M. Cetin, and A. S. Willsky, “A sparse signal reconstruction perspective for source localization with sensor arrays,” IEEE Transactions on Signal Processing, vol. 53, no. 8, pp. 3010-3022, Aug. 2005.

estimate(Y, k, l, solver_options={}, **kwargs)[source]

Estimates the source locations from the given measurements.

Parameters:
  • Y (ndarray) – The matrix of measurements, each column of which represents a single snapshot.
  • k (int) – Expected number of sources.
  • l (float) – The regularization parameter. Larger values of l usually leads to more sparse solutions, at the cost of increased biases.
  • solver_options (dict) – A dictionary of additional keyword arguments to be passed to the optimizer. For instance, you can specify the solver or set the verbosity.
  • return_spectrum (bool) – Set to True to also output the spectrum for visualization. Default value if False.
Returns:

A tuple with the following elements.

  • resolved (bool): True is the solver successfully obtained the sparse solution and the peak finder successfully identified the desired number of peaks. This flag does not guarantee that the estimated source locations are correct. The estimated source locations may be completely wrong! If resolved is False, both estimates and spectrum will be None.
  • estimates (SourcePlacement): A SourcePlacement instance of the same type as the one used in the search grid, represeting the estimated source locations. Will be None if resolved is False.
  • spectrum (ndarray): An numpy array of the same shape of the specified search grid, consisting of values evaluated at the grid points. Only present if return_spectrum is True.