핵 노름 최소화 IRLS의 엄밀한 우최소화(Majorization) 함수와 수렴률
Tight Majorizations and Convergence Rates of Nuclear Norm Minimization IRLS
한국어 초록
반복 재가중 최소제곱(IRLS, Iteratively Reweighted Least Squares) 방법은 핵 노름(nuclear norm) 최소화에 대한 자연스러운 접근법이지만, 그 수렴률과 가중치 연산자(weight operator)의 역할은 아직 충분히 이해되지 못했다. 본 논문은 저랭크 복원(low-rank recovery)에서 제약이 있는 핵 노름 최소화를 위한 IRLS 방법의 엄밀한(sharp) 수렴률을 규명한다. 핵심 요소는 평활화된 핵 노름(smoothed nuclear norm)에 대한 새로운 우최소화(majorization) 분석으로, 조화평균(harmonic-mean) 가중치 연산자가 유효한 전역 2차 우최소화 함수(global quadratic majorizer)를 정의함을 증명한다. 나아가 이 가중치 연산자가 멱평균(power-mean) 가중치 계열 내에서 최적임을 보이며, 이를 통해 행 공간 또는 열 공간 정보만 사용하는 기존의 단측(one-sided) 재가중 방식보다 개선되는 이유를 설명한다. Schatten-1 영공간 성질(null space property) 하에서, 조화평균 가중치를 포함한 다양한 가중치 연산자를 사용하는 IRLS 알고리즘의 전역 선형 수렴을 증명한다. 조화평균 가중치를 사용하는 IRLS에 대해서는 차원에 독립적인 국소 선형 수렴률을 증명한다. 또한 문헌에서 주로 사용되는 단측 가중치 연산자를 쓰는 IRLS 알고리즘에서는 이러한 차원 독립적 국소 수렴률을 일반적으로 얻을 수 없음을 보이는 반례를 제시한다. 수치 실험은 이론적 결과를 뒷받침하며, 정사각, 직사각, 그리고 적대적으로 초기화된 복원 문제 전반에서 조화평균 재가중의 실용적 이점을 보여준다.
원문 초록
Iteratively reweighted least squares (IRLS) methods constitute a natural approach to nuclear norm minimization, but their convergence rates and the role of the weight operator have remained poorly understood. This paper establishes sharp convergence rates for IRLS methods for constrained nuclear norm minimization in low-rank recovery. A central ingredient is a new majorization analysis for the smoothed nuclear norm: we prove that the harmonic-mean weight operator defines a valid global quadratic majorizer. Furthermore, we show that this weight operator is optimal within the family of power-mean weights, clarifying why it improves over classical one-sided reweighting schemes that use only row- or column-space information. Under a Schatten-1 null space property, we prove global linear convergence of IRLS algorithms using a variety of weight operators, including the harmonic-mean weights. For IRLS with harmonic-mean weights, we prove a dimension-independent, locally linear convergence rate. We provide a counterexample showing that this dimension-independent local rate cannot in general be obtained for IRLS algorithms using one-sided weight operators, which predominate in the literature. Numerical experiments corroborate the theoretical results and illustrate the practical advantage of harmonic-mean reweighting across square, rectangular, and adversarially initialized recovery problems.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2608.23765v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.