Fast Approximate Construction of Best Complex Antipodal Spherical Codes

Datum:

Dienstag, April 4, 2017 - 14:00 bis 15:45

Ort:

PB-H 0103

Vortragender:

Dr. Miguel Heredia Conde

Compressive Sensing (CS) theory states that real-world signals can often be recovered from

much fewer measurements than those suggested by the Shannon sampling theorem. Neverthe-

less, recoverability does not only depend on the signal, but also on the measurement scheme.

The measurement matrix should behave as close as possible to an isometry for the signals of

interest. Therefore the search for optimal CS measurement matrices of size m × n translates

into the search for a set of n m-dimensional vectors with minimal coherence. Best Complex

Antipodal Spherical Codes (BCASCs) are known to be optimal in terms of coherence. An

iterative algorithm for BCASC generation has been recently proposed that tightly approaches

the theoretical lower bound on coherence. Unfortunately, the complexity of each iteration de-

pends quadratically on m and n. In this work we propose a modification of the algorithm that

allows reducing the quadratic complexity to linear on both m and n. Numerical evaluation

showed that the proposed approach does not worsen the coherence of the resulting BCASCs.

On the contrary, an improvement was observed for large n. The reduction of the computatio-

nal complexity paves the way for using the BCASCs as CS measurement matrices in problems

with large n. We evaluate the CS performance of the BCASCs for recovering sparse signals.

The BCASCs are shown to outperform both complex random matrices and Fourier ensembles

as CS measurement matrices, both in terms of coherence and sparse recovery performance,

specially for low m/n, which is the case of interest in CS.

News