# Designing a fast linear operator with $\pm 1$ entries with low condition number and low Hamming distance between consecutive rows

I need to design a matrix for compressive imaging where each row represents an $N$-pixel filter in a focal plane through which light is masked, summed, and measured (think of Rice's single-pixel camera). The requirements are the following.

• There is cost associated with switching elements of the mask. Thus, the desire to limit the Hamming distance between consecutive rows/measurements (e.g., $25\%$ sign flips).

• A low condition number is desirable from an isometry perspective.

• It should be constructed, at least in part, with fast operators (e.g., Hadamard-Walsh transforms, circulant matrices) to speed iterative reconstruction.

Note that the constraints of minimizing the condition number and the Hamming distance are conflicting. For example, any set of orthogonal rows, as one would have with a Hadamard matrix, minimizes the condition number ($=1$), but all rows necessarily have a Hamming distance of $\frac N2$ (exactly half the signs flip between any pair of rows).

Does anyone have any ideas about prior art or insight how to approach this problem from a principled perspective?

### Update: circulant matrix approach

As Thomas Arildsen notes in the comments, if you create a circulant matrix from a length-$N$ vector $v$ that has $K$ sign changes, each row will vary from the previous row in exactly $\frac KN$ spots.

Furthermore, the matrix spectrum is equal to $\mbox{FFT}(v)$. This allows quick evaluation of condition number.

The problem is thus how to create the vector $\vec{v}$ with $K$ sign changes that minimizes the objective

$$\vec{v}^* = {\text{argmin} \\ \vec{v} \in \Gamma_K} \frac {\max_i |[\mathbf{F}\vec{v}]_i|^2} {\min_j |[{\mathbf{F}\vec{v}]_j|^2 }}$$

where

$$\Gamma_K \triangleq \{\vec{v} \text{ has K sign flips}\} \subset \{-1,+1\}^N\\ \mathbf{F} \text{ is FFT}$$

• Are you considering a data-driven approach where the matrix could be learned through dictionary learning or are you going exclusively for an "analytic" approach of optimizing coherence along with your Hamming objective? – Thomas Arildsen Aug 18 '18 at 20:59
• Just a thought so far: if you consider a circulant matrix, I guess your low Hamming distance between rows translates to correlated entries in (the) row such that the +1 or -1 tend to cluster together in runs of several identical symbols. – Thomas Arildsen Aug 18 '18 at 21:11
• How big is your matrix? – Rodrigo de Azevedo Aug 20 '18 at 16:34
• @RodrigodeAzevedo The operator (which would never be formed explicitly as a dense matrix) is on the order of one million by one million – Mark Borgerding Aug 20 '18 at 17:21
• Did you solve it? – David Mar 16 at 21:21