我國在統計物理思想的確定性算法求解壓縮取得進展

　　近期， 理論物理研究所周海軍研究員等對基于統計物理思想的確定性算法求解壓縮感知問題進行了深入的研究，取得了階段性的突破進展，論文于2018年2月28日發表于國際電氣和電子工程師協會的綜合性學報 IEEE Access上。

　　壓縮感知是一種新型數據采集和儲存方法，于2004年由陶哲軒等學者提出并引起科學和工程界的極大重視，現已在大數據稀疏特征提取、醫學影像診斷、遙感數據分析、機器學習等等領域被廣泛探討。壓縮感知的核心是欠定線性方程組 y = A x，其中 x 是 N 維未知矢量，y 是 M 維測量結果，A 是 M*N 維測量矩陣。由于測量數 M 遠小于數據維數 N，壓縮感知的目標是構造一個包含最多零元素的解 x，即尋找欠定線性問題的最稀疏解。這是極困難的組合優化問題。雖然文獻中已經有基于貪心思想、線性規劃、消息傳遞等不同思路的各類近似求解算法，但它們能發揮效果的前提是測量矩陣滿足苛刻的隨機不相干條件，即限制等距特性（restricted isometry property, RIP）。然而 RIP 條件在許多實際的壓縮感知應用問題上都不滿足。

　　面對這一挑戰，理論物理研究所周海軍研究員從統計物理角度對欠定線性稀疏求解問題重新進行了考察，發現該問題的容易獲得的最短稠密解包含了最稀疏解的極重要統計信息。基于這一洞察，周海軍和同事張潘副研究員及實習大學生沈牧天一起開發出最短稠密解引導下的最稀疏解構造方法 SSD (shortest-solution guided decimation)。該確定性算法與文獻中常用的經驗算法計算復雜度相同，但它能更好地求解欠定線性問題。最為突出的是，對于強關聯測量矩陣而言，SSD 是目前唯一已知的可行算法，意味著它可作為一種通用工具處理各類實際壓縮感知問題。該算法的統計物理理論及其在有噪聲壓縮感知上的拓展是要繼續研究的問題。 該交叉學科研究得到了中國科學院前沿科學重點研究項目、國家自然科學基金委創新群體基金,以及彭桓武理論物理創新研究中心、中國科學院理論物理前沿重點實驗室的聯合資助。