드문 선형 회귀 및 격자 문제

드문 선형 회귀(SLR)는 설계 행렬 X^{m n}과 응답 벡터 y=X^*+w가 주어지고, 여기서 k-드문 벡터 ^* (즉, \|^*\|₀ k)와 작은 무작위 노이즈 w가 있을 때, k-드문 Rⁿ을 찾아 평균 제곱 예측 오차 1m\|X-X^*\|²₂를 최소화하는 문제로, 통계학에서 잘 연구된 문제입니다. 설계 행렬이 잘 정규화된 경우, 기초 추구, Lasso, Dantzig 선택기와 같은 ₁-완화 방법이 SLR을 해결합니다. 하지만 모든 효율적인 알고리즘과 관련하여 평균 사례 설정에서의 어려움에 대한 일반적인 알고리즘이나 공식적인 증거는 없습니다. 우리는 격자 문제의 최악 사례 어려움을 가정하면서 모든 효율적인 알고리즘에 대한 SLR의 평균 사례 어려움의 증거를 제공합니다. 구체적으로, BDD(유한 거리 디코딩) 문제의 변형에서 SLR에 대한 인스턴스별 축소를 제시하며, BDD 인스턴스를 정의하는 격자 기초의 조건수는 설계 행렬의 제한 고유값 조건과 직접 관련이 있습니다. 이는 드문 선형 회귀를 위한 일부 고전적 통계-계산 격차를 특징짓습니다. 또한 격자 세계의 최악 사례에서 평균 사례로의 축소를 통해, 이는 SLR 인스턴스의 분포에 대한 어려움을 나타냅니다. 설계 행렬이 불량 조건을 가졌을 때, 결과 SLR 인스턴스는 식별 가능한 영역에 있습니다. 더욱이, Lasso가 식별 가능한 영역에서 잘 작동하는 것으로 알려진 잘 정규화된(본질적으로) 등방성 가우시안 설계 행렬에 대해, 우리는 많은 해결책이 존재하는 식별 불가능한 영역에서 어떤 좋은 해결책을 출력하는 것의 어려움을 보여줍니다.