Partially deterministic sampling for compressed sensing with denoising guarantees

1. 문제 정의 (Problem Statement)

압축 센싱 (Compressed Sensing, CS) 은 고차원 신호를 그 차원보다 훨씬 적은 수의 측정값으로 복원하는 기술입니다. 기존 연구에서는 주로 단위 행렬 (Unitary matrix, 예: 푸리에 행렬) 의 행 중 일부를 무작위 (Random) 로 선택하여 샘플링하는 방식을 사용했습니다.

그러나 실제 응용 분야 (예: MRI) 에서는 특정 측정 벡터 (예: 저주파 성분) 가 신호 복원에 결정적으로 중요하여, 이론적 무작위성 대신 결정론적 (Deterministic) 으로 샘플링해야 하는 경우가 많습니다.

• 기존 방법의 한계:
  • With-replacement (복원 추출): 중요 행이 샘플링되지 않거나 (missed), 동일한 행이 중복되어 샘플링될 수 있어 정보 효율이 떨어집니다.
  • Without-replacement (비복원 추출): 중복 샘플링은 피하지만, 여전히 중요한 고간섭 (high-coherence) 행이 우연히 누락될 수 있는 확률이 존재합니다.
  • 이론적 격차: 기존 이론은 무작위 샘플링에 집중되어 있어, 필수적인 행을 포함하는 부분적 결정론적 샘플링에 대한 엄밀한 이론적 보장 (특히 소음 제거 측면) 이 부족했습니다.

이 논문은 베르누이 선택자 (Bernoulli selectors) 를 사용하여, 중요한 행은 100% 확률 (결정론적) 로 포함하고 나머지는 확률적 으로 샘플링하는 최적화된 하이브리드 방식을 제안하며, 이에 대한 엄밀한 이론적 보장을 제공합니다.

2. 방법론 (Methodology)

저자들은 베르누이 샘플링 행렬을 정의하고, 이를 기반으로 한 최적화된 샘플링 가중치 계산 및 복원 이론을 개발했습니다.

• 베르누이 선택자 샘플링 (Bernoulli Selector Sampling):

  • 각 측정 행 $f_j$에 대해 독립적인 베르누이 확률 변수 $\xi_j \sim \text{Ber}(w_j)$를 사용합니다.
  • 가중치 $w_j=1$인 행은 반드시 샘플링 (결정론적) 되고, $w_j < 1$인 행은 확률적으로 샘플링됩니다.
  • 샘플링된 행의 개수는 무작위적이지만 기댓값은 $m$이 됩니다.

• 최적화된 가중치 도출 (Optimized Weights):

  • 국소 간섭성 (Local Coherence, $\alpha$): 신호의 사전 정보 (Prior set) 와 측정 행렬 간의 정렬 정도를 나타내는 벡터입니다.
  • 최적화 목표: 샘플링 복잡도 (Sample complexity) 를 최소화하는 가중치 $w^\circ$를 찾습니다.
  • 폐쇄형 해 (Closed-form Solution): 보조 방정식을 풀거나 최적화 문제를 반복적으로 푸는 대신, 국소 간섭성 벡터 $\alpha$와 측정 횟수 $m$을 기반으로 명시적인 공식으로 최적 가중치를 도출했습니다.
    • $w^\circ_j = \min\left( \frac{m \alpha_j^2}{L^2(\alpha, m)}, 1 \right)$
    • 여기서 $L(\alpha, m)$은 최적화된 복잡도 인자로, 포화 (saturation, $w_j=1$) 된 행의 간섭성을 제외하고 계산됩니다.

• 이론적 프레임워크:

  • 제한된 등거리 성질 (RIP): 베르누이 샘플링 행렬이 RIP 를 만족하는 조건을 증명했습니다.
  • 소음 민감도 (Noise Sensitivity): 가우시안 소음 하에서 복원 오차의 상한을 분석하기 위해 새로운 '단위 절단 연산자 (Unit Truncation Operator)'를 도입하여 소음 항을 제어했습니다.

3. 주요 기여 (Key Contributions)

1. 소음 제거 보장 (Denoising Guarantees):

   • 가우시안 소음과 변수 확률 가중치 하에서 베르누이 샘플링에 대한 최초의 소음 제거 (Denoising) 경계를 확립했습니다. 이는 기존 'With-replacement' 이론을 'Bernoulli' 설정으로 확장한 것입니다.

2. 명시적 최적 가중치 (Closed-form Probability Weights):

   • 최적의 베르누이 가중치를 계산하기 위해 보조 방정식이나 복잡한 최적화 문제를 풀 필요 없이, 명시적인 공식을 제공했습니다. 이는 구현을 단순화하고 국소 간섭성과 측정 수 간의 관계를 투명하게 만듭니다.

3. 개선된 샘플 복잡도 상한 (Improved Sample Complexity Bounds):

   • 기존 'With-replacement' 샘플링의 복잡도 인자 $\|\alpha\|_2$를 $L(\alpha, m)$으로 대체하여 더 강력한 상한을 제시했습니다.
   • $L(\alpha, m) \le \|\alpha\|_2$이며, 특히 $m$이 클 때 포화된 행 (중요한 행) 의 간섭성을 제외하므로 복잡도가 크게 감소함을 보였습니다.

4. 일반적인 베르누이 가중치에 대한 복원 보장:

   • 최적화된 가중치뿐만 아니라, 임의의 베르누이 가중치에 대한 복원 및 소음 제거 이론을 제공했습니다.

4. 실험 결과 (Results)

논문은 이론적 결과를 수치 실험으로 검증했습니다.

• 데이터셋: CELEBA (얼굴 이미지) 및 Flower 데이터셋을 사용했습니다.
• 사전 모델 (Priors):
  1. 희소성 (Sparsity): Haar 웨이블릿 기반의 3 단계 희소 신호.
  2. 생성 모델 (Generative): VAE(변분 오토인코더) 기반의 신경망 생성 모델.
• 비교 대상:
  • 최적화된 베르누이 샘플링 (Proposed)
  • 최적화된 With-replacement 샘플링
  • 최적화된 Without-replacement 샘플링 (Hoppe et al. 방식 포함)
  • 균일 무작위 샘플링 및 결정론적 샘플링
• 주요 발견:
  • 성능 우위: 제안된 최적화된 베르누이 샘플링은 대부분의 경우 다른 모든 방법보다 상대 오차가 낮게 나타났습니다.
  • 중요 행의 보장: Toy Example(6 절) 에서 보듯, Without-replacement 방식은 중요한 행 (예: $e_1$) 을 우연히 누락할 확률이 $n \to \infty$일 때도 일정하게 존재하는 반면, 베르누이 방식은 $w_j=1$로 설정하여 누락 확률을 0 으로 만들 수 있습니다.
  • 계산 효율성: Without-replacement 방식의 'Empirical Preconditioner'는 고간섭 행이 이미 샘플링된 후 남은 행을 샘플링하는 데 계산 비용이 기하급수적으로 증가하는 문제가 있었으나, 베르누이 방식은 이를 우회하여 효율적입니다.

5. 의의 및 결론 (Significance)

이 논문은 압축 센싱 분야에서 이론적 무작위성과 실용적 결정론적 요구사항 사이의 간극을 메우는 중요한 기여를 했습니다.

• 실용적 적용성: MRI 와 같이 특정 주파수 대역이 필수적인 응용 분야에서, 중요한 데이터를 우연에 맡기지 않고 확실하게 포함하면서도 나머지 데이터는 효율적으로 무작위 샘플링할 수 있는 이론적 토대를 마련했습니다.
• 이론적 발전: 베르누이 샘플링에 대한 엄밀한 RIP 및 소음 제거 보장을 제공함으로써, 향후 다양한 생성 모델 및 희소 신호 복원 문제에 이 방식을 적용할 수 있는 신뢰성을 높였습니다.
• 효율성: 샘플링 복잡도 상한을 개선하여, 동일한 복원 정확도를 달성하는 데 필요한 측정 횟수를 줄일 수 있음을 보였습니다.

요약하자면, 이 연구는 "중요한 행은 반드시 포함하고, 나머지는 지능적으로 무작위화하는" 최적화된 샘플링 전략을 제안하며, 이를 통해 압축 센싱의 복원 성능과 이론적 보장을 동시에 향상시켰습니다.