Recover a high dimensional vector x 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.
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 λ is given by
Mλ=2λ([[2λt+21]]−21)
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∈RN denote an s-sparse vector (∣∣x∣∣0≤s) with s<2N. We obtain mprojections of x as follows:
zi=[[⟨ai,x⟩]],i=1,2,⋯,m
Usually, $$m \leq N$$ in the compressed sensing paradigm. Stacking these projections, we get
z=[[y]]=[[Ax]]
The non-linearity introduced by the modulo operation along with the undetermined compressive measurements could lead to an indeterminate system.
P0: Any real valued vector y∈Rm can be uniquely decomposed as y=z+v where z∈[0,1)m and v∈Zm denote the fractional and integral part of y respectively. The following optimization problem is defined as P0
argx,vmin∥x∥0 subject to Ax=z+v;v∈Zm
Notice that v is the integral part and not z, which may be confusing.
z is the fixed fractional measurement, so it already lies in [0,1)m; the optimization is over x and v.
The ∥x∥0 objective encodes the sparsity assumption on x.
Any s′ sparse solution to P0 such that s′≤s is also s sparse.
Identifiability
Lemma. Every s-sparse vector is the unique minimizer of P0 iff, for every set S of 2s columns of A and every nonzero v∈Zm, the columns of AS together with v are linearly independent, where s<2N.
Proof.
(→) Suppose the condition fails for a set S of 2s columns: either AS is rank deficient or some nonzero integer vector lies in its span. In either case, there is a nonzero vector y supported on S such that
Ay=w∈Zm where y∈Rn 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)
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.
(←) Let z∈[0,1)m and v,v1∈Zm such that Ax=z+v and Ax1=z+v1 where ∥x∥0,∥x1∥0≤s. Now, the size of the support of x−x1 is at most 2s. Consequently,
A(x−x1)=v−v1∈Zm
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)×N, the column space of A contains no nonzero vector in ZN+1, so the modulo map x↦[[Ax]] is injective and every x is uniquely recoverable. With a square invertible A∈RN×N, a nonzero integer vector v gives the alias x−A−1v, so N+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 x satisfying ∥x∥0≤s as a unique solution to P0:
m≥2s+1, and
Any 2s columns of A are linearly independent.
In standard CS, uniform uniqueness requires at least 2s measurements and holds when every set of 2s columns is linearly independent; a generic matrix with m=2s rows meets this condition. We now show m=2s+1 measurements is sufficient for unique recovery.
Theorem. For any N≥2s+1, there exists a matrix A∈Rm×N with m=2s+1 rows such that every s-sparse x∈RN can be uniquely recovered from its modulo measurements z=[[Ax]]
Proof. We define the following
V={v∈Zm:v=0} denotes the countably infinite set of nonzero integer vectors.
G={T∣T⊂[N],∣T∣=2s} denotes the set of all index sets on [N] whose cardinality is 2s.
Let A be a matrix for which at least one s- sparse vector xcannot be recovered from z=[[Ax]] via (P0). Our aim is to show the set of all such matrices is of Lebesgue measure zero.
For a given u∈V and S∈G, construct B(u,S)=[uAS]. If det(B(u,S))=0, then the columns of AS together with u are linearly dependent. This function is a non-zero polynomial of the entries of As, 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}, This set is of Lebesgue measure zero (why?). Therefore, any matrix A chosen outside this set will ensure that any s-sparse vector x can be recovered from y=[[Ax]].
If the entries of A are drawn independently from any continuous distribution, A 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) be a function with no frequencies higher than Ω(rad/s), then a sufficient condition for recovery of f(t) from its modulo samples yk=Mλ(f(t)),t=kT,k∈Z is,
>T≤2Ωe1>
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<π/Ω.
Theorem. Let f(t) be a finite-energy function with no frequencies higher than Ω (rad/s). Then the function f(t) is uniquely determined by its modulo samples yk=Mλ(f(tk)) taken on grid t=kTϵ,k∈Z where
>0<Tϵ<Ω+ϵπ,ϵ>0>
Convex Relaxation
Replacing the l0-norm in P0 with the l1-norm, we obtain the optimization problem:
P1:argx,vmin∥x∥1 subject to Ax=z+v;v∈Zm
Integer Range Space Property
A matrix A is said to satisfy the IRSP of orders if, for all sets S⊂[N] with ∣S∣≤s,
∥uS∥1<∥uSc∥1
holds for every u∈RN with Au=v∈Zm.
Theorem. Every s-sparse x is the unique solution of (P1) iff the matrix A satisfies the IRSP of order s.
Proof.
(→) Consider a fixed index set S with ∣S∣≤s, and suppose that every x supported on S is a unique minimizer of (P1). Then, for any u such that Au=v∈Zm, the vector uS is the unique minimizer of (P1). But, A(uS+uSc)∈Zm. This means that −uSc is also a solution of (P1) for [[AuS]]=y. Consequently, (we are talking about l1-norm not l0-norm)
∥uS∥1<∥uSc∥1
(←) Suppose IRSP holds with respect to the set S. Consider x supported on S and another vector x1 that result in the same modulo measurements with respect to A. Let u=x−x1, the vector Au∈Zm. Due to the IRSP,
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) containing disjoint intervals, the Lebesgue measure is defined by
μL(S)=k∑(bk−ak)
Refer to this [document](https://math.unl.edu/~gmeisters1/papers/Measure/measure.pdf) for more details regarding this topic.
Let A⊆R. A is said to be of measure zero if for any ϵ>0, there exists a sequence of open intervals (In)n∈N such that,
A⊆n=1⋃∞In and n=1∑∞l(In)<ϵ
where, $$l((a, b)) = b - a$$. For example, $$\mathbb{Q}$$ is of measure zero.