← All notes

Modulo Compressed Sensing

Contents
  1. Compressed Sensing
  2. Identifiability
  3. Conditions for recovery
  4. Convex Relaxation
  5. Mixed Linear Integer Program (MILP)

Compressed Sensing

Recover a high dimensional vector xx with a very few non-zero values. Plethora of algorithms

Sensors and Measurements

  • Sensors have Finite Dynamic Range

  • Loss of information due to clipping. One potential approach to fix this is to wrap around the signal.

    image-20210610112718042​

This is where Modulo comes in.

Why can’t we scale the signal?

There is an inherent quantization step involved during measurements. Therefore, scaling down and scaling back up will have the same resolution.

  • Quantization error is proportional to the maximum value of the input signal.

Modulo Compressed Sensing

Typically, the real world sensors have a finite dynamic range. They have a clipping effect where the measurements become saturated once the values cross the range of the sensor. High dynamic range systems are affected by high quantization noise. To counter this problem, a new approach for measurements called self-reset analog to digital converters (SR-ADCs) have been proposed.

These sensors fold the amplitudes back into the dynamic range of the ADCs using the modulo arithmetic. However, these systems encounter loss due to the modulo operation. The transfer function of the SR_ADC with parameter λ\lambda is given by

Mλ=2λ([[t2λ+12]]−12)\mathcal M_\lambda = 2\lambda \left( \left[ \left[ \frac{t}{2\lambda} + \frac{1}{2} \right]\right] - \frac{1}{2}\right)
Here, $$[[t]] \triangleq t - \lfloor t \rfloor$$ denotes the fractional part of $$t$$. Now, we need to consider how we shall sample the values. A sampling theory called *unlimited sampling framework* was developed which provides sufficient conditions on the sampling rate for guaranteeing the recovery of band-limited signals from the folded samples. SR-ADC is applied individually to multiple linear measurements of the images, and is termed as modulo compressed sensing.

Note. The measured values may lie outside the dynamic range due to sensor noise.

Let us concretely define the problem. Let x∈RNx \in \mathbb{R}^N denote an ss-sparse vector (∣∣x∣∣0≤s||x||_0 \leq s) with s<N2s < \frac{N}{2}. We obtain mm projections of xx as follows:

zi=[[⟨ai,x⟩]],i=1,2,⋯ ,mz_i = [[ \langle a_i, x \rangle ]], i = 1,2, \cdots, m
Usually, $$m \leq N$$ in the compressed sensing paradigm. Stacking these projections, we get
z=[[y]]=[[Ax]]z = [[y]] = [[Ax]]
The non-linearity introduced by the modulo operation along with the undetermined compressive measurements could lead to an indeterminate system.

P0\mathbf{P_0}: Any real valued vector y∈Rmy \in \mathbb{R}^m can be uniquely decomposed as y=z+vy = z + v where z∈[0,1)mz \in [0, 1)^m and v∈Zmv \in \mathbb{Z}^m denote the fractional and integral part of yy respectively. The following optimization problem is defined as P0P_0

arg⁡min⁡x,v∥x∥0 subject to Ax=z+v;v∈Zm\arg \min_{x,v} \|x\|_0 \\ \text{ subject to } Ax = z + v; v \in \mathbb Z^m
  • Notice that vv is the integral part and not zz, which may be confusing.
  • zz is the fixed fractional measurement, so it already lies in [0,1)m[0, 1)^m; the optimization is over xx and vv.
  • The ∥x∥0\|x\|_0 objective encodes the sparsity assumption on xx.
  • Any s′s' sparse solution to P0P_0 such that s′≤ss' \leq s is also ss sparse.

Identifiability

Lemma. Every ss-sparse vector is the unique minimizer of P0P_0 iff, for every set SS of 2s2s columns of AA and every nonzero v∈Zmv \in \mathbb Z^m, the columns of ASA_S together with vv are linearly independent, where s<N2s < \frac{N}{2}.


Proof.

(→\rightarrow) Suppose the condition fails for a set SS of 2s2s columns: either ASA_S is rank deficient or some nonzero integer vector lies in its span. In either case, there is a nonzero vector yy supported on SS such that

Ay=w∈Zm where y∈Rn has support SAy = w \in \mathbb{Z}^m \text{ where } y\in \mathbb{R}^n \text{ has support } S
Consider a vector $$x$$ defined from $$y$$ whose support is the first $$s$$ columns of $$S$$. Similarly, define $$x_1$$ whose support is the remaining $$s$$ columns of $$S$$. Let $$Ax = z + v$$ where $$z \in [0, 1)^m$$ and $$ v \in \mathbb{Z}^m$$. We have
Ax1=Ay−Ax=w−(z+v)Ax_1 = Ay - Ax = w - (z + v)
Therefore, $$-x_1$$ and $$x$$ are distinct feasible $$s$$-sparse vectors with identical modulo measurements. At least one is not the unique $$\ell_0$$ minimizer, contradicting uniform recovery. This proves necessity.

(←\leftarrow) Let z∈[0,1)mz \in [0, 1)^m and v,v1∈Zm v, v_1 \in \mathbb{Z}^m such that Ax=z+vAx = z + v and Ax1=z+v1 Ax_1 = z + v_1 where ∥x∥0,∥x1∥0≤s\|x\|_0, \|x_1\|_0 \leq s. Now, the size of the support of x−x1x - x_1 is at most 2s2s. Consequently,

A(x−x1)=v−v1∈ZmA(x - x_1) = v - v_1 \in \mathbb{Z}^m
For a distinct competing solution $$x_1 \neq x$$, extend the support of $$x-x_1$$ to a set $$S$$ of $$2s$$ columns. If $$v-v_1=0$$, the columns of $$A_S$$ are linearly dependent; otherwise, the nonzero integer vector $$v-v_1$$ lies in their span. Either case contradicts the condition that the columns of $$A_S$$ together with every nonzero integer vector are linearly independent. This proves sufficiency.

Corollary. For generic A∈R(N+1)×NA \in \mathbb R^{(N+1)\times N}, the column space of AA contains no nonzero vector in ZN+1\mathbb Z^{N+1}, so the modulo map x↦[[Ax]]x \mapsto [[Ax]] is injective and every xx is uniquely recoverable. With a square invertible A∈RN×NA \in \mathbb R^{N\times N}, a nonzero integer vector vv gives the alias x−A−1vx-A^{-1}v, so N+1N+1 measurements are necessary for generic universal recovery.

Conditions for recovery

Signals in spacial domain

To compare the modulo-CS problem to the standard CS problem, we state the two necessary conditions for modulo-CS recovery.

The following two conditions are necessary for recovering any vector xx satisfying ∥x∥0≤s\|x\|_0 \leq s as a unique solution to P0P_0:

  • m≥2s+1m \geq 2s + 1, and
  • Any 2s2s columns of AA are linearly independent.

In standard CS, uniform uniqueness requires at least 2s2s measurements and holds when every set of 2s2s columns is linearly independent; a generic matrix with m=2sm=2s rows meets this condition. We now show m=2s+1m = 2s + 1 measurements is sufficient for unique recovery.

Theorem. For any N≥2s+1N \geq 2s + 1, there exists a matrix A∈Rm×NA \in \mathbb{R}^{m \times N} with m=2s+1m = 2s + 1 rows such that every ss-sparse x∈RNx \in \mathbb{R}^N can be uniquely recovered from its modulo measurements z=[[Ax]]z = [[Ax]]


Proof. We define the following

  1. V={v∈Zm:v≠0}\mathcal{V} = \{v \in \mathbb{Z}^m : v \neq 0\} denotes the countably infinite set of nonzero integer vectors.
  2. G={T∣T⊂[N],∣T∣=2s}\mathcal{G} = \{T \vert T \subset [N], \vert T\vert = 2s\} denotes the set of all index sets on [N][N] whose cardinality is 2s2s.

Let AA be a matrix for which at least one ss- sparse vector xx cannot be recovered from z=[[Ax]]z = [[Ax]] via (P0)(P_0). Our aim is to show the set of all such matrices is of Lebesgue measure zero.

For a given u∈Vu \in \mathcal{V} and S∈GS \in \mathcal{G}, construct B(u,S)=[uAS]B(u, S) = \begin{bmatrix}u&A_S\end{bmatrix}. If det⁡(B(u,S))=0\det(B(u, S)) = 0, then the columns of ASA_S together with uu are linearly dependent. This function is a non-zero polynomial of the entries of AsA_s, and therefore the set of matrices which satisfy this condition have Lebesgue measure zero.

Now, consider ∪S∈G∪u∈V{A∣det(B(u,S))=0}\cup_{S \in \mathcal{G}}\cup_{u \in \mathcal{V}} \{ A \vert det(B(u, S)) = 0 \}, This set is of Lebesgue measure zero (why?). Therefore, any matrix AA chosen outside this set will ensure that any ss-sparse vector xx can be recovered from y=[[Ax]]y = [[Ax]].


  • If the entries of AA are drawn independently from any continuous distribution, AA lies outside the set of Lebesgue measure 0 described in the above theorem.
  • Integer matrices cannot be used as candidate measurement matrices for modulo CS (why?)

Signals in Temporal domain

Unlimited Sampling Theorem - A band-limited signal can be recovered from modulo samples provided that a certain sampling density criterion is satisfied. This criterion must be independent of the ADC threshold.

Theorem. Let f(t)f(t) be a function with no frequencies higher than Ω\Omega(rad/s), then a sufficient condition for recovery of f(t)f(t) from its modulo samples yk=Mλ(f(t)),t=kT,k∈Zy_k = \mathcal M_\lambda(f(t)), t = kT, k \in \mathbb Z is,

>T≤12Ωe>> T \leq \frac{1}{2\Omega e} >

The above guarantees the recovery of the signal. Now, we discuss the conditions for unique recovery. There is a one-to-one mapping between a band-limited function and its modulo samples provided that the sampling rate is higher than the Nyquist Rate, T<π/ΩT < \pi/\Omega.

Theorem. Let f(t)f(t) be a finite-energy function with no frequencies higher than Ω\Omega (rad/s). Then the function f(t)f(t) is uniquely determined by its modulo samples yk=Mλ(f(tk))y_k = \mathcal M_\lambda(f(t_k)) taken on grid t=kTϵ,k∈Zt = kT_\epsilon, k \in \mathbb Z where

>0<Tϵ<πΩ+ϵ,ϵ>0>> 0 < T_\epsilon < \frac{\pi}{\Omega + \epsilon}, \epsilon > 0 >

Convex Relaxation

Replacing the l0l_0-norm in P0P_0 with the l1l_1-norm, we obtain the optimization problem:

P1:arg⁡min⁡x,v∥x∥1 subject to Ax=z+v;v∈Zm\mathbf{P_1} :\arg \min_{x, v} \|x\|_1 \\ \text{ subject to } Ax = z + v; v \in \mathbb{Z}^m

Integer Range Space Property

A matrix AA is said to satisfy the IRSP of order ss if, for all sets S⊂[N]S \subset [N] with ∣S∣≤s\vert S\vert \leq s,

∥uS∥1<∥uSc∥1\|u_S\|_1 < \|u_{S^c}\|_1

holds for every u∈RNu \in \mathbb{R}^N with Au=v∈ZmAu = v \in \mathbb{Z}^m.

Theorem. Every ss-sparse xx is the unique solution of (P1)(P_1) iff the matrix AA satisfies the IRSP of order s.


Proof.

(→\rightarrow) Consider a fixed index set SS with ∣S∣≤s\vert S\vert \leq s, and suppose that every xx supported on SS is a unique minimizer of (P1)(P_1). Then, for any uu such that Au=v∈ZmAu = v \in \mathbb Z^m, the vector uSu_S is the unique minimizer of (P1)(P_1). But, A(uS+uSc)∈ZmA(u_S + u_{S^c}) \in \mathbb Z^m. This means that −uSc-u_{S^c} is also a solution of (P1)(P_1) for [[AuS]]=y[[Au_S]] = y. Consequently, (we are talking about l1l_1-norm not l0l_0-norm)

∥uS∥1<∥uSc∥1\|u_S\|_1 < \|u_{S^c}\|_1

(←\leftarrow) Suppose IRSP holds with respect to the set SS. Consider xx supported on SS and another vector x1x^1 that result in the same modulo measurements with respect to AA. Let u=x−x1u = x - x^1, the vector Au∈ZmAu \in \mathbb Z^m. Due to the IRSP,

∥uS∥1<∥uSc∥1\|u_S\|_1 < \|u_{S^c}\|_1

Hence,

∥x∥1≤∥x−xS1∥1+∥xS1∥1=∥uS∥1+∥xS1∥1<∥uSc∥1+∥xS1∥1=∥−xSc1∥1+∥xS1∥1=∥x1∥1\begin{align} \|x\|_1 &\leq \|x - x^1_S\|_1 + \|x^1_S\|_1 \\ &= \|u_S\|_1 + \|x^1_S\|_1 \\ &< \|u_{S^c}\|_1 + \|x^1_S\|_1 \\ &= \|-x^1_{S^c}\|_1 + \|x_S^1\|_1 = \|x^1\|_1\end{align}
Thus proving uniqueness.

Mixed Linear Integer Program (MILP)

The l1l_1-norm can be re-written as a linear function using two positive vectors x+x^+ and x−x^-, where x=x+−x−x = x^+ - x^-. This leads to the MILP formulation

min⁡x+,x−,v1T(x++x−) subject to [A−A−I][x+x−v]=z;v∈Zm;x+,x−≥0\min_{x^+, x^-, v} \mathbf{1}^T(x^+ + x^-) \\ \text{ subject to } \\ \begin{bmatrix}A&-A&-I\end{bmatrix}\begin{bmatrix}x^+ \\ x^- \\ v\end{bmatrix} = z; \\ v\in \mathbb Z^m; x^+, x^- \geq 0
This is efficiently solved using [branch-and-bound algorithm](https://towardsdatascience.com/the-branch-and-bound-algorithm-a7ae4d227a69).

Appendix - Lebesgue Measure

Lebesgue measure is an extension of the classical notions of length, area and volume to more complicated sets. Given an open set S≡∑k(ak,bk)S \equiv \sum_k (a_k, b_k) containing disjoint intervals, the Lebesgue measure is defined by

μL(S)=∑k(bk−ak)\mu_L(S) = \sum_k(b_k - a_k)
Refer to this [document](https://math.unl.edu/~gmeisters1/papers/Measure/measure.pdf) for more details regarding this topic.

Let A⊆RA \subseteq \mathbb{R}. AA is said to be of measure zero if for any ϵ>0\epsilon > 0, there exists a sequence of open intervals (In)n∈N(I_n)_{n \in \mathbb{N}} such that,

A⊆⋃n=1∞In and ∑n=1∞l(In)<ϵA \subseteq \bigcup\limits^\infty_{n = 1}I_n \text{ and } \sum_{n = 1}^\infty l(I_n) < \epsilon
where, $$l((a, b)) = b - a$$. For example, $$\mathbb{Q}$$ is of measure zero.
Type to search the whole site.