cr.sparse.cs.cs1bit.biht

cr.sparse.cs.cs1bit.biht(Phi, y, K, tau, max_iters=1000)

Solves the 1-bit compressive sensing problem $$\begin{gathered} \text{sgn}( \\ Phix)=y \end{gathered}$$ using Binary Iterative Hard Thresholding

Parameters

• Phi (jax.numpy.ndarray) – A random dictionary of shape (M, N)

• y (jax.numpy.ndarray) – The 1-bit measurements

• K (int) – Sparsity level of solution x (number of non-zero entries)

• tau (float) – Step size for the x update step

• max_iters (int) – Maximum number of iterations

Returns

A named tuple containing the solution x and other details

Return type

(BIHTState)

We assume that $x$ is a K-sparse vector.

We assume that the one-bit measurements are made as follows:

(1)$$y=\text{sgn}(\mathrm{\Phi }x)$$

Thus the vector y contains entries 1 and -1 for the signs of the entries in the measurement $\mathrm{\Phi }x$.

The BIHT algorithm proceeds as follows:

• Start with an estimate $x=0$

• Compute the guess $\hat{y}=\text{sgn}(\mathrm{\Phi }x)$

• Measure the residual $r=y-\hat{y}$

• Count the number of mismatched bits as number of places where r is non-zero.

• Compute the correlation $h={\mathrm{\Phi }}^{T}r$

• Update x as $x=x+\frac{\tau }{2}h$

• Hard threshold x to keep only K largest entries

• Repeat till convergence

Example

>>> import cr.sparse as crs
>>> import cr.sparse.dict as crdict
>>> import cr.sparse.data as crdata
>>> import cr.sparse.cs.cs1bit as cs1bit
>>> M, N, K = 256, 512, 4
>>> Phi = crdict.gaussian_mtx(cnb.KEYS[0], M, N, normalize_atoms=False)
>>> x, omega = crdata.sparse_normal_representations(cnb.KEYS[1], N, K)
>>> x = x / norm(x)
>>> y = cs1bit.measure_1bit(Phi, x)
>>> s0 = crdict.upper_frame_bound(Phi)
>>> tau = 0.98 * s0
>>> state = cs1bit.biht_jit(Phi, y, K, tau)
>>> x_rec = build_signal_from_indices_and_values(N, state.I, state.x_I)
>>> x_rec = x_rec / norm(x_rec)