Structured Compressed Sensing: From Theory to Applications

Marco F. Duarte; Yonina C. Eldar

Source-linked AI summary

Structured Compressed Sensing: From Theory to Applications

Marco F. Duarte, Yonina C. Eldar

arXiv:1106.6224v22011년 6월 30일cs.IT

TL;DR

Structured compressed sensing는 실제 acquisition에서 conventional random-measurement와 standard-sparsity model의 한계를 다룬다. 이 review는 structured sensing architecture, 더 풍부한 signal model, application을 종합해 CS theory와 hardware를 연결하며, signal structure를 활용하면 resolution을 높일 수 있다고 결론짓는다.

문제
기존 CS review는 주로 randomized discrete-to-discrete measurement와 standard sparsity에 초점을 맞추지만, 실제 system에는 structured architecture와 더 폭넓은 signal model이 필요하다.
방법
이 review는 measurement와 signal structure를 반영하는 CS 확장을 survey하며, elaborate sensing scheme, joint-sparse model, application-oriented formulation을 포함한다.
결과
이 review는 signal structure를 활용하면 resolution을 높이고 random-measurement paradigm을 넘어 practical sensing을 지원할 수 있음을 보여주는 대표적인 theory와 application을 요약한다.
시사점 및 한계
Structured CS는 feasible hardware constraint와 더 풍부한 signal model을 practical signal acquisition 및 processing과 연결하는 framework를 제공한다.

Abstract

from arXiv · show

Compressed sensing (CS) is an emerging field that has attracted considerable research interest over the past few years. Previous review articles in CS limit their scope to standard discrete-to-discrete measurement architectures using matrices of randomized nature and signal models based on standard sparsity. In recent years, CS has worked its way into several new application areas. This, in turn, necessitates a fresh look on many of the basics of CS. The random matrix measurement operator must be replaced by more structured sensing architectures that correspond to the characteristics of feasible acquisition hardware. The standard sparsity prior has to be extended to include a much richer class of signals and to encode broader data models, including continuous-time signals. In our overview, the theme is exploiting signal and measurement structure in compressive sensing. The prime focus is bridging theory and practice; that is, to pinpoint the potential of structured CS strategies to emerge from the math to the hardware. Our summary highlights new directions as well as relations to more traditional CS, with the hope of serving both as a review to practitioners wanting to join this emerging field, and as a reference for researchers that attempts to put some of the existing ideas in perspective of practical applications.

I. 서론 및 동기 … A. 희소성

이 리뷰는 sub-Nyquist acquisition을 signal 및 measurement structure와 연결해 structured compressed sensing의 필요성을 제시한 뒤, CS를 linear dimensionality reduction과 sparsity에서 더 폭넓은 signal model 및 실제 hardware로 확장한다. 또한 structured CS를 mathematical recovery theory, 실현 가능한 acquisition architecture, application을 잇는 가교로 위치시킨다.

I. 서론 및 동기: Structured CS는 완전히 random한 measurement matrix를 wireless channel, analog hardware, sensor network, optical imaging을 반영하는 application-dependent architecture로 대체한다.이는 CS가 기존의 단순화된 discrete-to-discrete 설정을 넘어 확장된 데 따른 변화다.
A. Shannon-Nyquist 정리: Shannon-Nyquist reconstruction은 bandlimited signal에 대해 최소 2B의 등간격 sampling을 요구하지만, 점점 넓어지는 wideband application에서는 이러한 변환 속도를 가용한 ADC hardware로 구현하기 어렵다.Structured analog signal은 Shannon-Nyquist framework가 내부 structure를 고려하지 않기 때문에 잠재적으로 더 효율적으로 처리할 수 있다.
I. 서론 및 동기: 이 리뷰는 signal structure를 활용하는 acquisition device를 대상으로 하며, sampling, storage, DSP가 전체 signal dimension이 아니라 information content에 의존하도록 한다.핵심 목표는 structured CS strategy를 mathematical theory에서 실제 hardware와 application으로 옮기는 데 있다.
B. Compressed Sensing과 그 너머: CS는 M ≪ N개의 linear measurement로 N-dimensional signal을 복원하며, 신중하게 선택한 projection vector를 통해 acquisition 과정에서 compression을 수행한다.이 리뷰는 union-of-subspaces model 및 관련 structured signal representation 을 통해 이 framework를 standard sparsity 너머로 확장한다.
III. Compressed Sensing 기초: CS measurement model은 M < N인 조건에서 y = Φx를 acquisition하며, 선택한 class의 signal이 실질적으로 더 적은 measurement만으로 유일하게 식별되도록 Φ를 설계한다.따라서 recoverable signal class는 compressed sensing에서 핵심적인 design choice다.
A. 희소성: Sparsity는 x = Ψθ와 같이 signal을 K ≪ N개의 nonzero coefficient만으로 표현하며, O(K log2 N) bits를 사용해 coefficient의 값과 위치를 보존함으로써 compression을 가능하게 한다.Sparsity는 가장 널리 사용되는 CS structure이며, imaging denoising, deconvolution, restoration, inpainting을 포함한 transform-coding application을 뒷받침해 왔다.
A. 희소성: Power-law coefficient decay를 보이는 approximately sparse signal은 K가 증가할수록 최선의 K-term approximation error가 감소하므로 s-compressible하다.CS는 이 structure를 활용해 measurement로부터 x를 복원하면서 M을 가능한 한 K에 가깝게 낮추고자 한다. 이 리뷰에서는 x 자체가 sparse하도록 identity basis를 자주 사용한다.

B. CS 행렬 설계

CS 행렬 설계는 sparse signal의 유일하고 안정적인 복원을 목표로 하며, spark 기반 유일성에서 계산 가능한 coherence 및 RIP 보장으로 발전해 왔다. 또한 이 절에서는 deterministic construction과 randomized matrix, 그리고 실용적인 structured alternative를 대비한다.

B. CS 행렬 설계: spark(Φ) > 2K이면 모든 measurement vector는 최대 하나의 K-sparse signal에 대응하므로, 필요한 measurement 조건은 M ≥ 2K가 된다.Spark는 선형 종속인 column 중 최소 개수를 측정하지만, 이를 계산하는 데는 조합적 복잡도가 따른다.
B. CS 행렬 설계: Coherence는 더 쉽게 계산할 수 있는 유일성 기준을 제공하며, Gershgorin circle theorem과 Welch bound를 통해 pairwise column correlation과 spark의 관계를 구해 얻는다.그 결과인 coherence 기반 sparsity 보장은 scaling 측면에서 더 약하며, 이 절에서 보고한 바와 같이 K = O(√M)이다.
B. CS 행렬 설계: (K, δ)-RIP는 모든 M × K submatrix가 거리를 근사적으로 보존하도록 하며, additive noise가 있을 때 안정성을 뒷받침하고, Φ가 (2K, δ)-RIP를 가지며 δ > 0일 때 유일성을 보장한다.측정 전에 noise가 추가되면 recovery distortion은 N/M배 악화된다.
B. CS 행렬 설계: Deterministic matrix는 강한 spark, coherence 또는 RIP 특성을 제공할 수 있지만, Vandermonde matrix는 condition이 나빠지고 일부 RIP construction은 M = O(K^2 log N)개의 measurement를 요구한다.이러한 한계 때문에 실제 N과 K 값에서는 이런 construction이 바람직하지 않다.
B. CS 행렬 설계: Random Gaussian, Rademacher 및 subgaussian matrix는 높은 확률로 spark, coherence 또는 RIP 보장을 달성하며, subsampled Fourier와 Hadamard transform도 효과적인 CS recovery를 지원한다.이러한 randomized 및 structured construction은 deterministic design의 한계를 보완하고, 논의되는 실용적 matrix 선택지를 넓힌다.

C. CS 복구 알고리즘

CS 복구 알고리즘은 측정값과 정확히 또는 근사적으로 일치하는 신호를 탐색하며, 복구 보장과 계산적 실현 가능성 사이의 균형을 추구한다. 이 절에서는 전수 ℓ0 탐색과 convex ℓ1 방법, 잡음 인식 확장, 확률적 사전분포 접근법, greedy 반복 알고리즘을 대조한다.

희소 복구 정식화: ℓ0 최소화는 y와 일치하는 가장 희소한 신호를 탐색하며, 희소해의 유일성하에서 모든 x ∈ΣK에 대해 성공하지만 조합적 복잡도를 갖는다.이 탐색은 Φ의 K개 열로 이루어진 모든 집합의 span을 확인해야 할 수 있으므로, 계산적으로 실현 가능한 대안이 필요하다.
Convex 최적화: Basis pursuit는 ℓ0을 convex ℓ1 norm으로 대체하여, 신호 길이에 대해 polynomial complexity를 갖는 linear-program 구현을 가능하게 한다.BP는 가장 희소한 해 문제의 convex relaxation으로 정식화된다.
잡음 인식 복구: 잡음이 있는 측정값 y = Φx + n에 대해 BP는 잡음 크기 bound를 사용하는 BPIC와 Lagrangian relaxation을 통한 BPDN으로 확장되며, polynomial-complexity solver가 존재한다.BP, BPIC, BPDN에 대해 효율적인 solver를 사용할 수 있다.
Stochastic 잡음 모델: bounded-norm 잡음이 지나치게 비관적인 경우, complexity-based regularization 과 Bayesian estimation 은 complexity-based 또는 probabilistic prior를 통해 stochastic noise를 반영한다.일반적인 stochastic model은 additive white Gaussian noise n ∼N(0, σ2I)이다.
Greedy 복구: matching pursuit와 orthogonal matching pursuit 같은 Greedy methods는 수렴 기준을 충족할 때까지 측정 잔차와 가장 높은 상관을 갖는 Φ의 열을 반복적으로 선택한다.OMP는 각 반복에서 support, signal estimate, residual을 갱신한다.

D. CS 복원 보장

CS 복원 보장은 사용된 matrix metric 또는 signal model에 따라 coherence, RIP, non-uniform probabilistic conditions로 구성된다. Randomized matrix와 sparse-signal model은 K = O(M)에서 복원을 가능하게 하며, K = O(√M)인 deterministic coherence-based 보장보다 향상된 성능을 제공한다.

Coherence-based 보장: Coherence-based 결과는 noiseless 또는 noisy measurement에서 BP와 OMP의 복원을 보장하지만, noisy error bound는 noise magnitude에 따라 scale하며 그 크기에 대한 지식을 요구한다.OMP는 support 보장을 위해 minimum nonzero coefficient의 lower bound도 요구하지만, BPIC와 BPDN은 그렇지 않다.
Coherence-based 보장: AWGN에서 BPDN은 O(σ√K log M)의 error bound를 달성하며, deterministic noise-magnitude 보장을 적용해 얻는 O(σ√M) bound보다 상당히 작고 Cramér–Rao bound에 가깝다 [61, 62].OMP도 coherence 및 minimum-entry 조건하에서 AWGN에 대해 high-probability error와 exact-support recovery를 달성할 수 있다.
Non-uniform 보장: Non-uniform probabilistic 보장은 matrix 요구 조건을 완화하고 충분히 sparse한 signal 대부분을 복원하며, support와 entries가 명시된 random model을 따를 때 high probability로 unique BP recovery도 가능하게 한다.이러한 보장은 모든 signal에 uniformly 적용되는 것이 아니라 sparse signal의 부분집합에 적용된다.
Measurement scaling: RIP 또는 probabilistic sparse-signal model에서 high-probability recovery를 위해 K = O(M)이 필요하며, deterministic coherence 보장에서는 K = O(√M)이 필요해 square root bottleneck이 발생한다.이러한 scaling 향상은 randomized CS matrix와 sparse signal model의 인기를 설명하는 데 도움이 된다.

IV. CS 행렬의 구조 · A. 부분표본화된 비간섭 기저

Structured CS는 측정 물리와 하드웨어에 의해 제약되는 sensing architecture로, 구현 불가능한 임의 random matrix를 대체하며 신호의 sparsity basis와 비간섭적인 부분표본화 기저를 포함한다. 이 접근법은 적절한 orthonormal basis에서 계수를 선택해 measurement를 구성하고, 계수 선택을 통해 제한적인 randomness를 유지한다.

IV. CS 행렬의 구조: 현실의 sensing physics와 device capabilities는 구현 가능한 CS matrix를 제한할 수 있다.임의의 고차원 matrix–vector multiplication은 실제 applications에서 비용이 너무 클 수 있다.
IV. CS 행렬의 구조: Structured CS matrix는 독립적으로 random화된 matrix entry의 실용적 한계를 해결한다.Sensing modality와 hardware가 실현 가능한 measurement architecture를 결정한다.
A. 부분표본화된 비간섭 기저: Sparsity basis와 비간섭적인 basis는 그 계수를 부분표본화해 CS measurement를 제공할 수 있다.이는 coherence 개념을 하나의 frame에서 orthonormal basis 쌍으로 확장한다.
A. 부분표본화된 비간섭 기저: 부분표본화-비간섭 기저 구성은 measurement로 사용되는 계수의 선택을 통해 어느 정도 randomness를 유지한다.어떤 basis coefficient가 신호를 표현할지 선택하는 과정에 randomness가 남아 있다.
A. 부분표본화된 비간섭 기저: 형식적으로 measurement는 열이 서로 다른 basis element를 나타내는 주어진 N × N basis Φ를 사용한다.주어진 formulation은 Φ = [φ1 φ2 . . . φN]으로 basis를 정의한다.
A. 부분표본화된 비간섭 기저: 열 submatrix는 measurement vector y를 구성하기 전에 Γ로 index된 basis vector를 보존한다.주어진 formulation은 index set Γ를 통해 보존되는 basis element를 정의한다.

1) 정식화: … 2) 이론적 보장:

이 framework는 mutual coherence를 통해 structured compressed sensing을 평가하고, recovery guarantee를 sparse signal에서 compressible signal로 확장한다. 또한 structurally subsampled matrix, hardware 제약 acquisition, imaging과 compressive ADC를 포함한 응용을 분석한다.

1) 정식화:: Mutual coherence는 두 orthonormal basis의 원소 사이에서 가장 큰 absolute inner product를 측정하며, 값은 Fourier basis와 canonical basis의 N^-1/2부터 shared element의 1까지이다.이 정의는 continuous-time signal의 infinite-dimensional representation으로 확장된다.
1) 정식화:: Random sign과 uniformly sampled measurement를 사용할 때, Theorem 14는 M ≥ CKNµ^2(Φ, Ψ) log(N/δ)이고 M ≥ C′ log^2(N/δ)일 때 K-sparse signal을 확률 1 −δ 이상으로 exact recovery할 것을 보장한다.필요한 measurement 수는 O(K log N)에서 O(N)까지이다.
2) 이론적 보장:: Compressible signal의 경우 Rudelson과 Vershynin의 논증을 조정하면 coherence와 restricted isometry가 연결되어, 확률 1−5e^−t 이상에서 δ_2K ≤1/2를 얻으며 measurement 요구량은 µ(Φ, Ψ)에 의해 결정된다.이 결과는 sparse-signal guarantee를 compressible signal로 확장한다.
2) 이론적 보장:: Subsampled incoherent basis는 MRI, tomographic imaging, optical microscopy에서 hardware-limited measurement를 지원하며, 이때 acquisition은 2-D continuous Fourier coefficient를 직접 생성한다.이 응용들은 structured acquisition architecture의 주요 범주 중 하나를 이룬다.
3) 응용:: 두 번째 범주는 hardware-compatible measurement basis를 설계하는 것으로, binary optical-modulator pattern을 사용하는 single-pixel camera와 uniform frequency grid상의 periodic multitone signal을 위한 random sampling ADC를 포함한다.Randomized basis permutation은 wavelet과의 coherence를 줄이며, single-pixel camera의 optical aggregation은 measurement signal-to-noise ratio를 향상한다.
B. Structurally Subsampled Matrices: Structurally subsampled matrix는 여러 signal coefficient를 선형 결합하는 observation을 모델링하며, Φ는 Φ = RU에서 row를 무작위로 선택하고 normalize하여 구성된다.P = N이고 R = I일 때 subsampled incoherent basis를 포함한다.
2) 이론적 보장:: 인접한 transform coefficient를 합산하는 integrator matrix와 Rademacher diagonal modulation을 사용하면, 결과 structurally subsampled matrix는 확률 1 −20 max{exp(−c2δ^2z), N^−1} 이상에서 (K, δ)-RIP를 만족한다 [83].이 구성은 R = SM을 사용하며, S는 인접 coefficient의 interval을 aggregate한다.
2) 이론적 보장:: Coherence µ(U, Ψ)는 structurally subsampled matrix의 measurement 요구량을 결정하며, 그 범위는 O(K log^3 N)에서 O(N)까지이다.이는 subsampled incoherent-basis 설정과 평행한다.

3) 응용: … 1) 정식화:

이 논문은 실현 가능한 acquisition hardware와 compressive sensing을 연결하는 structured sensing architecture를 개발하며, analog random demodulation, subsampled circulant matrix, imaging system, separable multidimensional measurement를 아우른다. 이러한 구조는 자유도 또는 계산 비용을 줄이는 동시에 특수한 이론적 보장을 요구하고 더 풍부한 signal model을 수용한다.

3) 응용:: Structured CS는 일반적인 random matrix를 hardware-compatible operator로 대체하며, 균일하게 격자화된 주파수가 유한차원 model을 형성하는 주기적 multitone analog signal을 대상으로 한다.Random demodulator는 pseudorandom chipping sequence와 signal을 혼합하여 analog domain에서 matrix multiplication을 효과적으로 구현한다.
3) 응용:: Random demodulation은 representation의 maximal frequency에 의해 실용적으로 제한되며, 보고된 구현은 1 MHz에 도달하므로 백만 개의 coefficient가 필요하다.Prototype 및 관련 구현은, 에 보고되어 있다.
3) 응용:: Infinite-dimensional signal model은 finite-parameter random demodulation보다 효율적인 analog acquisition과 digital processing으로 compressive sensing을 확장할 수 있다.이러한 adaptation의 세부 사항은 Section VI로 미룬다.
C. Subsampled Circulant Matrix: Subsampled circulant sensing은 circulant matrix의 행을 무작위로 선택하여 Φ = RU를 구성하고, channel estimation 및 activity detection과 같은 communication task에서 matrix의 자유도를 줄인다.이러한 응용은 channel response 또는 multiuser activity pattern에 sparse prior를 사용한다.
2) 이론적 보장:: Circulant entry는 서로 dependent하므로 standard independent-entry proof를 적용할 수 없으며, recovery guarantee에는 대안적인 probabilistic tool과 defining sequence의 randomness가 필요하다.제공된 이론적 구절은 universal constant C와 C′를 포함한 명시된 bound 아래에서 높은 확률로 RIP를 달성할 수 있다고 기술한다.
3) 응용:: Convolution-based sensing은 Φ와 ΦT에 대한 FFT multiplication을 통해 빠른 CS computation을 지원하며, dense point spread function을 사용하는 imaging system에 구현할 수 있다.Dense PSF는 imaging field 전체에 impulse를 확산시켜 coded aperture를 이용한 compressive imaging을 가능하게 한다.
3) 응용:: Custom microelectronic imager는 N × N sensor array와 N^2-length feedback shift register를 사용하여 subsampled circulant CS matrix를 구현한다.이 architecture는 pseudorandom generator, LFSR-controlled multiplier, quantization을 사용하며, schematic은 Fig. 5에 제시되어 있다.
D. Separable Matrix: Separable matrix와 Kronecker-product matrix는 각 dimension에서 structure와 sparsity 또는 compressibility를 활용하여 multidimensional signal에 효율적인 CS representation을 제공한다.x = Ψθ이고 Ψ = Ψ1 ⊗ … ⊗ ΨD일 때, component matrix의 RIP property는 full matrix에 대한 대응 bound를 제공한다 [96, 97].

2) 이론적 보장: … 1) measurement matrix 조건:

이 논문은 structured sensing과 joint-sparse recovery에 대한 이론적 보장을 전개한 뒤, separable CS matrix를 hyperspectral 및 transform-imaging hardware와 연결한다. 또한 표준 sparsity를 넘어 structured finite-dimensional 및 continuous-time signal model로 CS의 범위를 확장한다.

2) 이론적 보장:: orthonormal basis Φ_d에 대해 Kronecker-product sensing matrix는 Φ_d의 δ_d=0 때문에 CS matrix의 RIP constant를 그대로 물려받는다.이는 structured measurement construction에서도 관련 RIP 보장을 유지한다.
2) 이론적 보장:: Kronecker product는 mutual coherence를 보존하므로, 명시된 recovery theorem에 따르면 partitioned measurement보다 크지 않은 measurement requirement를 얻는다.각 section의 sparsity와 measurement-basis coherence가 모두 1 이하이기 때문에 이러한 비교가 성립한다.
3) 응용:: Separable CS matrix는 hyperspectral datacube와 transform-imaging architecture를 포함한 multidimensional sensing application을 지원한다.Hyperspectral 예제는 single-pixel camera를 확장하며, transform imager는 tiled matrix product를 통해 separable matrix를 구현한다.
3) 응용:: Spectrometer-based hyperspectral camera는 spectral band 전반에 shared modulation pattern을 적용하여, separable sensing matrix로 표현되는 measurement를 생성한다.Spectrometer는 wavelength별 intensity를 기록하고, micromirror array는 관심 대상인 모든 wavelength를 반사한다.
V. FINITE-DIMENSIONAL MODEL의 STRUCTURE: Measurement structure를 넘어, 이 논문은 finite-dimensional model의 sampling을 줄이고 궁극적으로 continuous-time signal까지 다루도록 sparsity를 일반화한다.논의는 먼저 finite-dimensional vector에서 nonzero value를 구조화한 뒤, Section VI에서 더 넓은 analog-signal model로 확장한다.
A. Multiple Measurement Vectors: MMV recovery는 common support를 공유하는 vector를 joint하게 추정하며, 이를 최대 K개의 nonzero row를 갖는 matrix로 표현한다.Model은 Y=ΦX이고 각 measurement vector는 signal dimension보다 짧으며, shared support information을 joint하게 활용할 수 있다.
1) measurement matrix 조건:: MMV uniqueness는 rank와 support에 의존하며, necessary-and-sufficient condition에 따르면 higher-rank matrix는 더 적은 measurement 또는 더 큰 support에서 recovery할 수 있다.rank(X)=1이면 joint processing이 이점을 제공하지 않으며, 더 큰 column diversity는 recovery 이점을 가능하게 한다. 또한 noiseless recovery에는 간단한 algorithm이 존재한다.

2) 복원 알고리즘: · 3) 성능 보장:

MMV 시스템의 복원 방법은 mixed-norm 최적화와 greedy 알고리즘부터 rank-aware, ReMBo, continuous-to-finite 전략까지 다양하며, sparsity, rank, measurement 조건에 따라 보장이 달라진다. Average-case 분석에 따르면 joint recovery는 더 적은 measurement를 필요로 하며 worst-case 한계를 넘어 높은 확률로 복원할 수 있다.

2) 복원 알고리즘:: Mixed-norm recovery는 ℓ0 목적함수를 Y = ΦX 제약하에서 ∥X∥p,q를 최소화하는 문제로 대체하며, simultaneous greedy 방법은 residual-matrix q-norm에서 행을 선택하도록 OMP를 확장한다.권장되는 선택은 p, q = 1, 2, ∞이며, greedy 확장은 residual vector를 residual matrix로, ΦT r을 ΦT R의 row q-norm으로 대체한다.
2) 복원 알고리즘:: ReMBo는 sparsity pattern을 유지하면서 MMV를 SMV로 축소한 뒤 support를 복원하고 measurement를 역변환하며, 반복적인 random reduction으로 경험적 복원율을 높일 수 있다.이 축소는 measurement column을 random coefficient로 결합하지만, noise나 불충분한 measurement로 인해 오류가 발생할 수 있다.
2) 복원 알고리즘:: Rank-aware recovery는 rank(X) = K이고 condition (31)이 성립할 때 X를 정확히 복원하며, signal subspace를 활용해 support를 식별한다.Noise 환경에서는 subspace criterion을 최소화하는 K개 index를 선택해 rank-aware 방법을 구성하며, rank가 증가할수록 성능이 향상된다.
2) 복원 알고리즘:: Continuous-to-finite reduction은 condition (31)에서 유일한 sparse solution이 원래 support를 갖는 finite MMV system을 풀어 infinite measurement-vector signal을 복원한다.이 축소는 measurement의 span에 대한 basis를 구성한 뒤, 식별된 support에서 pseudoinversion을 수행해 각 signal vector를 복원한다.
2) 복원 알고리즘:: MMV 확장은 SMV와 동등한 worst-case 보장을 제공하지만, multichannel reconstruction은 channel을 독립적으로 복원하는 것보다 실제로 더 나은 성능을 보인다.따라서 임의의 X에 대한 이론적 동등성만으로는 joint sparsity에서 관찰되는 실제 성능 향상을 예측할 수 없다.
3) 성능 보장:: Average-case 분석에서는 exact recovery에 더 적은 measurement가 필요하며, p = 2와 q = 1인 mixed-norm recovery는 K ≤ min(C1/µ2(Φ), C2N/∥Φ∥2)일 때 높은 확률로 성공한다.이 model은 K개의 nonzero row를 균일하게 random으로 선택하고, 이들의 concatenated nonzero entry를 Gaussian construction에서 추출한다.
3) 성능 보장:: Average-case recovery는 worst-case의 K = O(√M)에 비해 K = O(M) 차수까지 sparsity를 지원하며, failure probability는 channel 수 L에 따라 지수적으로 감소한다 [119].이 지수적 감소는 sparsity와 sensing matrix Φ에 대한 완화된 조건에서 성립한다.
3) 성능 보장:: MMV model은 EEG/MEG 응용도 지원하며, temporal regularization을 통해 주어진 signal sequence의 estimation을 추가로 개선할 수 있다.전자기 source signal을 localize하기 위해 sparsity-promoting inversion을 사용한다.

4) 응용: · B. 부분공간의 합집합 · 1) 측정 행렬의 조건:

이 절에서는 희소성을 유한 및 무한 차원 부분공간의 합집합으로 일반화하여, 표준 support를 넘어서는 구조적 신호 모델을 다룬다. 이어 이러한 모델을 위한 측정 조건, 복원 보장, block-sparse 정식화를 전개한다.

4) 응용:: MMV 복원은 특정 무한 차원 신호 모델에도 적용되며, 추가 논의는 Section VI-B로 미룬다.이 논문은 306개 센서와 120 ms 동안 세 vertex에서 시뮬레이션한 활동을 사용해 temporal regularization 기반 MMV EEG inversion을 예시로 제시한다.
B. 부분공간의 합집합: 부분공간의 합집합은 희소 신호를 여러 K-dimensional 부분공간 중 하나에 속하는 벡터로 나타내며, 표준 희소성을 더 풍부한 유한 및 무한 차원 모델로 확장한다.표준 희소 support는 coordinate axis에 정렬된 부분공간에 해당하지만, 다른 선택은 더 폭넓은 신호 prior를 부호화한다.
B. 부분공간의 합집합: 합집합 모델은 덧셈에 대해 닫혀 있지 않으므로, 합집합에 속하는 두 신호의 합은 일반적으로 합집합을 벗어나며, sampling과 복원이 복잡해진다.이러한 비선형 거동은 선형 신호 모델과 구별되는 핵심 특징이다.
B. 부분공간의 합집합: 유한 부분공간 합집합에는 구조적 희소 support와 부분공간의 희소 합이 포함되며, 선택된 support 패턴이나 부분공간 조합만 허용된다.이러한 경우들은 서로 결합할 수도 있으며, 무한 차원이거나 부분공간이 무한히 많은 모델은 analog 신호로 확장된다.
1) 측정 행렬의 조건:: 차원이 D인 L개 부분공간의 유한 합집합에 대해, subgaussian 측정 행렬은 명제에 제시된 조건하에서 적어도 1 −e−t의 확률로 (U, δ)-RIP를 만족한다.지배적인 점근적 측정 항은 신호의 정확한 부분공간을 식별하는 데 필요한 샘플 수를 정량화한다.
1) 측정 행렬의 조건:: 구조적 support 제약은 허용되는 support가 더 적기 때문에 전통적 희소성에 비해 필요한 측정 수를 줄이지만, 각 부분공간은 D = K 차원을 유지한다.부분공간의 희소 합에서는 nonzero 개수가 변하지 않으므로 D = O(K)는 감소하지 않는다.
1) 측정 행렬의 조건:: 부분공간의 희소 합은 block-sparse coefficient vector와 동등하며, 최대 K개의 nonzero block을 갖는 측정 y = AΨθ = Φθ를 산출한다.block size d = 1이면 block sparsity는 conventional sparsity로 환원되며, block-coherence는 coherence를 확장하고 µB(Φ) ≤µ(Φ)이다.

2) 복원 알고리즘:

구조적 희소 모델의 복원은 구조적 support 근사를 통합해 greedy 및 optimization 기반 방법을 확장하며, 수정된 조건에서 standard 알고리즘의 보장을 유지하는 경우가 많다. 이러한 방법에는 model-based CoSaMP와 IHT, block-thresholding 근사, 그리고 subspace 합에 대한 mixed-norm convex 복원이 포함된다.

Model-based greedy 복원: Model-based CoSaMP는 구조적 operator를 통해 residual과 signal pruning을 수정하며, 동일한 접근법으로 model-based IHT 변형도 도출된다.FUS 복원에서는 CoSaMP의 standard RIP requirement인 order 4K가 확장된 subspace union에 의존하는 조건으로 대체된다.
구조적 희소 근사: 구조적 희소 근사 알고리즘은 block sparsity를 포함한 다양한 support model에서 실행 가능하고 computationally efficient하며, MU는 energy가 가장 큰 K개 block을 보존한다.Block sparsity에서 MU는 block energy 또는 ℓ2 norm에 기반한 block thresholding과 동등하다.
Optimization 기반 복원: 희소 subspace 합의 경우 convex 복원은 mixed ℓ2/ℓ1 norm을 사용해 block energy의 합을 최소화한다.그 결과의 optimization formulation은 coefficient representation θ를 복원하며, 인용된 방법은 과 관련된다.
확장: Noisy measurements에서는 convex constraint를 완화할 수 있으며, greedy 복원도 block-sparse setting으로 일반화되었다.이러한 확장은 standard BPIC의 noise 처리와 병행된다.
보장: 많은 FUS 복원 방법은 CoSaMP의 경우처럼 model-specific requirement를 조건으로 standard counterpart의 보장을 계승하며, CoSaMP에서는 확장된 subspace union이 요구된다.제시된 CoSaMP 조건은 order 4K의 RIP를 요구하는 조건에서 비롯된다.

3) 복원 보장: · 4) 응용: · VI. 무한차원 모델의 구조

Structured model은 model-based RIP, optimization, block-coherence 조건에서 복원 보장을 제공하며, 응용 사례는 structured source separation과 내부적으로 sparse한 표현을 보여준다. 이 framework는 hardware-aware한 continuous-time formulation을 통해 reduced-rate analog sampling을 유한차원 또는 무한차원 부분공간들의 합집합으로 확장한다.

3) 복원 보장:: sensing operator가 (S4(U), δ)-RIP with δ ≤ 0.1을 만족할 때, model-based CoSaMP는 유한 개 부분공간 합집합에 속한 noisy signal을 복원한다.관련 보장은 model-based IHT에도 적용되며, 추가 조건을 통해 signal mismodeling에 대한 안정성도 확보된다.
3) 복원 보장:: 부분공간들의 sparse sum에 대한 optimization-based recovery는 bounded measurement noise가 존재하는 (S2(U), δ)-RIP 조건에서 보장된다.추정값은 relaxed constrained formulation으로부터 얻어지며, bound는 model mismatch quantity MU(x)에 따라 달라진다.
3) 복원 보장:: Block-coherence 조건은 greedy 및 optimization-based method 모두를 사용한 block-sparse vector의 복원을 보장하며, adversarial 및 random measurement noise로의 확장도 포함한다.Orthonormal block에서는 ν(Φ)=0이며, block structure를 활용하면 conventional sparsity보다 잠재적으로 더 높은 sparsity level에서 복원을 보장할 수 있다.
3) 복원 보장:: Tree-structured wavelet supports는 smooth 또는 piecewise-smooth signal을 위한 structured sparse model을 제공하며, 40000개 measurement로부터 얻은 512 × 512 Peppers image에 model-based CoSaMP를 적용한 결과가 제시된다.해당 figure는 동일한 image와 measurement에 대한 standard 및 model-based CoSaMP 복원을 대조하며, standard method에 대해서만 보고된 SNR이 제공된다.
4) 응용:: Subspace block 내부에 ℓ1 penalty를 추가하면 C-HiLaSo가 구성되며, structured representation을 위해 group-level sparsity와 individual-feature sparsity를 결합한다.Subsampled information에서 얻은 handwritten digit mixture에 적용했을 때, FUS model은 source identification과 separation을 지원하며, Fig. 10은 recovered digit과 active set을 보여준다.
VI. 무한차원 모델의 구조: Infinite-dimensional union model은 다음 세 경우를 통해 analog signal의 reduced-rate sampling을 다룬다: infinite-dimensional space의 finite union, finite-dimensional space의 infinite union, infinite-dimensional space의 infinite union.이 review는 각 class에 대해 general theory와 대표적인 application을 전개한다.
VI. 무한차원 모델의 구조: Analog-sampling approach는 signal을 subspace들의 union으로 직접 표현하며, hardware를 간과하거나 reduced-rate analog processing을 high-rate DSP로 옮길 수 있는 discretization-based method와 대조된다.Shift-invariant subspace가 도입부의 sampling framework를 제공하고, 이후 structure와 hardware-aware acquisition을 포함하도록 확장된다.

A. 아날로그 신호를 위한 shift-invariant spaces … 5) 응용 예:

이 논문은 shift-invariant 및 union-of-subspaces 신호 모델을 위한 구조화된 아날로그 compressed-sensing 아키텍처를 개발하여, 하드웨어 호환 측정과 Nyquist 미만 multiband sampling을 통한 복원을 가능하게 한다. 이 프레임워크는 아날로그 aliasing, 디지털 subspace identification, MMV 기반 reconstruction, 실용적인 sampling 대안을 결합한다.

A. 아날로그 신호를 위한 shift-invariant spaces: Shift-invariant spaces는 bandlimited, spline, multiband, pulse-amplitude-modulation 신호를 포함한 광범위한 아날로그 신호 클래스를 유한 개의 generator와 coefficient sequence로 표현한다.신호 공간이 무한 차원이어도 각 신호는 N/T 속도의 sample로 복원할 수 있다.
B. 무한 차원 subspace의 유한 union: 이 프레임워크는 K개의 generator만 활성화하거나 유한 또는 무한 집합에서 generator를 선택함으로써 shift-invariant 모델을 subspace의 union으로 확장한다.일반적인 아키텍처는 sampling 전에 신호에 aliasing을 적용하여 측정값에 모든 subspace 성분의 energy가 포함되도록 한 뒤, 복원 전에 활성 subspace를 식별한다.
1) 아날로그 신호 모델:: K개의 활성 generator를 알고 있으면 적절히 filtering된 K개의 uniform sample stream으로 충분하며, 알 수 없으면 문제는 단일 generator subspace의 union에서 복원하는 문제로 바뀐다.이는 compressive acquisition의 기반이 되는 아날로그 신호 모델을 정립한다.
2) Compressive signal acquisition scheme:: Compressive acquisition은 p<N개의 sampling filter를 Nyquist-rate reconstruction filter의 선형 결합으로 설계하며, 계수는 sparsity K를 갖는 discrete MMV 문제를 푸는 p×N matrix로 결정된다.임의의 invertible filter-bank matrix를 사용하면 sampling filter 선택에 추가적인 자유도가 생긴다.
3) Reconstruction algorithm:: Sampling된 generator coefficient는 jointly K-sparse measurement vector를 이루므로, 필요한 inverse filter-bank preprocessing 후 아날로그 복원은 MMV reconstruction 문제로 환원된다.Measurement vector는 p개의 sampled output을 모으며, unknown vector는 N개의 generator coefficient를 포함한다.
4) Recovery guarantees:: p=2K개의 filter는 모든 입력 신호에 대한 복원을 보장하지만, 실용적인 polynomial-time MMV algorithm은 일반적으로 2K보다 약간 많은 filter를 요구한다.Noise, mismodeling, suboptimal-recovery 결과는 기저가 되는 MMV 문제에서 그대로 전달된다.
5) 응용 예:: Carrier를 알 수 없는 multiband 신호에서 blind sampling density는 D(R)≥min{Ω, 2fmax}를 따르며, Ω=2NB이고 NB<fmax이면 Nyquist rate보다 낮은 sampling이 가능하다.Periodic nonuniform sampling은 partial DFT sensing matrix를 사용하여 이 lower bound에 근접할 수 있는 반면, modulated wideband converter는 PNS에 필요한 high-bandwidth track-and-hold를 피한다.

6) 하드웨어 예시: … 2) 압축 신호 획득:

이 논문은 modulated wideband converter를 통해 structured compressed sensing과 실제 하드웨어를 연결하고, finite-rate-of-innovation pulse model을 통해 analog signal recovery와 연결한다. 이러한 접근법은 신호 구조를 활용해 Nyquist-rate acquisition보다 훨씬 적은 샘플로 wideband 또는 continuous-time signal을 복원한다.

6) 하드웨어 예시:: carrier frequency가 알려진 경우 modular MWC는 channel 수 또는 sampling rate를 줄일 수 있으며, channel이나 rate를 추가해 full-band Nyquist sampling으로 확장할 수도 있다.Advanced configuration은 각 channel의 sampling rate를 같은 배수만큼 높이는 동시에 branch를 q배 축소한다.
6) 하드웨어 예시:: modulated wideband converter는 wideband input을 병렬 low-rate channel에서 mixing, filtering, sampling하여 spectrum slice의 compressed measurement를 생성한다.주기적 mixing은 spectrum slice를 뒤섞고, lowpass filtering은 필요한 narrowband mixture를 보존한다.
6) 하드웨어 예시:: MWC prototype은 2 GHz Nyquist rate와 120 MHz occupied spectrum을 갖는 43개 input을 총 280 MHz rate에서 sampling했으며, q = 3 hardware collapsing을 사용했다.이는 가장 높은 주파수가 아니라 occupied bandwidth에 비례하는 sampling을 보여준다.
C. 유한 차원 부분공간의 무한 합집합: generator가 unknown continuous parameter를 갖는 signal은 finite-dimensional subspace의 infinite union을 이루며, 여기에는 unknown delay와 amplitude를 갖는 pulse stream이 포함된다.pulse shape을 알고 있을 때 pulse-stream model은 2L degrees of freedom을 가지며, finite-rate-of-innovation model로 도입되었다.
1) Analog signal model:: full continuous-parameter model에 대한 일반적인 acquisition method가 존재하지 않으므로, 논의는 periodic pulse stream과 그 Fourier-series structure에 초점을 둔다.주기성은 model의 dimensionality를 보존하면서 acquisition을 더 쉽게 분석할 수 있게 한다.
2) 압축 신호 획득:: τ-periodic pulse stream의 경우, 선택한 Fourier sample이 pulse spectrum의 zero를 피하면 N ≥ |K| ≥ 2L일 때 filtered uniform sample이 signal을 유일하게 결정한다.sampling filter 뒤에 T = τ/N인 uniform sampling을 적용하며, 그 결과는 기존 lowpass-filter 연구를 arbitrary filter로 확장한다.
2) 압축 신호 획득:: Fourier coefficient는 matrix-pencil, subspace 또는 annihilating-filter method를 통해 delay와 amplitude의 recovery를 지원하며, 각 방법에는 2L coefficient가 필요하다.sample vector는 sampling scheme을 통해 필요한 Fourier-coefficient vector로 변환된다.
2) 압축 신호 획득:: Sum-of-Sincs filter는 finite-time-support acquisition을 제공하며 L = 100과 같은 매우 높은 pulse-stream order에서도 안정적이다. 이는 높은 L에서 spline-based moment와 대조된다.Infinite-time-support lowpass filter는 time-limited pulse stream을 직접 처리할 수 없으므로 SoS와 같은 compact filter가 필요하다.

3) 복원 알고리즘:

복원은 구조화된 sampling과 algebraic reconstruction을 결합한다. samples에서 Fourier coefficients를 얻은 뒤 annihilating filter로 pulse delays를 복원하고, Vandermonde inversion으로 amplitudes를 계산한다. Gaussian pulse 5개에서는 SoS-filter reconstruction이 samples 11개로 수치 정밀도까지 정확하며, Fig. 15는 여러 sampling kernel에 대한 noisy recovery를 비교한다.

SoS sampling은 samples에서 Fourier coefficient vector를 x = Q†c로 복원한다. 여기서 Q는 filter와 multichannel architecture의 경우 modulation coefficients에 의해 결정된다.
annihilating-filter 방법은 그 z-transform의 roots에서 delays를 식별한 뒤, 복원된 delays로부터 Fourier coefficients를 계산한다.
annihilating filter를 결정하고 delays를 복원하는 데에는 X[k]의 연속된 2L개 값만 필요하다.
관련 Vandermonde matrix가 left-invertible이므로 pulse amplitudes는 matrix inversion으로 얻는다.
수치 정밀도까지 정확하게, SoS-filter sampling은 N = 11 samples에서 L = 5 Gaussian pulse로 이루어진 signal을 복원한다. 또한 Fig. 15는 Gaussian [6], B-spline, E-spline [7], SoS kernel을 사용한 Dirac pulse 3개와 5개의 finite stream에 대한 noisy recovery를 비교한다.

4) 응용: … 2) 압축 신호 획득:

이 논문은 구조화 compressed sensing을 유한 차원 모델에서 superresolution, 초음파 영상, continuous-time 신호 획득 분야의 응용으로 확장한다. 또한 finite-rate-of-innovation 구조, 주기적 지연, 병렬 채널, digital filter correction을 활용하는 sampling 및 reconstruction 기법을 개발한다.

4) 응용:: FRI 기반 방법은 저해상도 영상을 먼저 정합한 뒤 더 높은 해상도의 출력으로 융합하여 image superresolution을 지원하며, blur와 noise를 제거할 가능성이 있다.고품질 superresolved image를 얻으려면 정합이 중요하며, Fig. 16은 8× superresolution factor를 보여준다.
4) 응용:: 초음파 영상은 FRI sampling을 사용해 획득 및 처리 부담을 줄이는 동시에 원래 recording보다 훨씬 fewer samples로 신호를 복원할 수 있다.Fig. 17은 원래의 4160-sample 신호와 N = 17 및 N = 33 samples를 사용한 복원을 비교한다.
D. 무한 차원 부분공간들의 무한 합집합: 무한 차원 공간들의 무한 합집합에서는 각 generator에 unknown parameter가 할당되며, 논의는 shifted generators hℓ(t) = h(t − τℓ)에 특화된다.논문은 전체 모델에 적용할 수 있는 일반적인 sampling framework가 현재 존재하지 않는다고 설명한다.
1) Analog signal model:: 길이 T인 각 구간에서 겹치지 않는 pulse가 L개 이하로 발생하면, 앞서 제시한 기법을 사용해 parameter를 독립적으로 처리할 수 있다.sampling system은 p ≥ 2K개의 채널을 사용하며 각 채널에서 T초마다 하나의 sample을 얻는다.
1) Analog signal model:: T를 넘어 연장되는 pulse의 경우 독립적인 주기별 처리는 실패하지만, periodic time delay를 사용하면 h(t)가 time limited가 아니더라도 single filter로 효율적인 sampling과 recovery가 가능하다.periodic-delay 경우는 특별한 단순화로 다루는 반면, amplitude는 비주기적으로 유지된다.
1) Analog signal model:: infinite-generator 설정에서는 유한 모델의 CTF block을 continuity를 지원하는 block으로 대체하며, ESPRIT가 사실상 CTF를 대체한다.이는 구조화된 SI 접근법을 N개의 가능한 generator에서 무한히 많은 가능성으로 확장한다.
2) Compressive signal acquisition:: compressive acquisition architecture는 p개의 parallel channel, band-limited kernel, 1/T에서의 uniform sampling, W^-1(e^jωT)를 통한 digital filter correction을 사용한다.kernel은 low-rate sampling 전에 시간상 신호 에너지를 분산시키며, 해당 filter는 single-channel rate의 p배로 sampling되는 하나의 filter로 통합할 수 있다.

3) 복원 알고리즘: … VII. 결론

이 논문은 연속시간 매개변수화 신호를 위한 구조적 복원 방법과 보장을 개발하고, radar 등의 응용에서 sampling rate를 낮추고 resolution을 향상시키는 한편 analog acquisition과 digital array processing을 연결한다.

3) 복원 알고리즘:: 제안된 ESPRIT 기반 복원은 correlation matrix를 구성하고, SVD로 signal subspace를 추출하며, eigenvalue를 계산한 뒤 이를 미지의 delay에 대응시킨다.digital correction 후 sample vector는 delay에 의존하는 Vandermonde matrix를 통해 amplitude와 관련되므로 ESPRIT 복원이 가능하다 [19, 173].
4) 복원 보장:: 필터가 요구되는 support를 가지며 W(e^jωT)가 invertible이면, 제시된 형태의 모든 신호는 p ≥ 2L − η + 1일 때 복원 가능함이 보장된다.이 보장은 signal vector가 η차원의 minimal subspace에 속하는 joint output에 적용된다.
4) 복원 보장:: 그 결과 sampling rate는 최대 2L/T이며 (L+1)/T까지 낮아질 수 있고, pulse Nyquist rate와 무관하므로 wideband를 크게 줄일 수 있다.이러한 감소는 output을 MMV와 유사한 방식으로 joint processing한 결과다.
5) 응용:: W ≥ 4πL/T이고 N ≥ 2 max Kℓ이면 radar target을 정확히 식별할 수 있으며, 최소 input time-bandwidth product는 WT ≥ 8πL max Kℓ이다.Doppler shift와 reflection coefficient는 복원된 sequence에서 standard spectral estimation tool을 사용해 얻는다.
5) 응용:: 서로 가까운 radar target 9개를 정확히 식별했으며, compressive union-of-subspaces 방법은 동일한 time-bandwidth product에서 matched filtering보다 low-noise resolution이 우수했다.비교는 delay–Doppler plane과 Fig. 19에 제시된 parameter를 사용한다.
E. 논의: 이러한 infinite-union 방법은 analog filter 뒤에 standard digital array processing을 사용하고, noise가 없을 때 perfect recovery를 달성하며, 일반적으로 noise가 존재해도 점진적으로 성능이 저하된다.noise 거동은 array-processing 문헌에서 광범위하게 분석되었다.
VII. 결론: 이 review는 device constraint, structured signal, continuous-time model, analog-to-digital interface, application-specific recovery algorithm을 포함함으로써 compressed sensing을 random measurement와 standard sparsity를 넘어 확장한다.선정된 사례는 theoretical foundation과 다양한 응용의 균형을 이루며, signal acquisition과 processing 분야의 실무자를 지원하기 위한 것이다.
VII. 결론: signal structure를 활용하면 compressed sensing은 radar, microscopy, surveillance, medical imaging 및 기타 ADC 의존 응용에서 resolution을 높이고 Nyquist barrier를 잠재적으로 제거할 수 있다.결론은 이를 resolution-limited system에서 사용 가능한 degrees of freedom을 효율적으로 활용하는 것으로 설명한다.