Abstract
低ランク行列回復問題は、未知のn_1 \times n_2 の階数が r の行列を、m 個の線形測定から復元しようとする問題であり、ここで m\ll n_1n_2 です。この問題はここ数十年にわたって広く研究されており、理論的保証がしっかりしたさまざまなアルゴリズムが提案されています。その中でも、勾配降下法に基づく非凸手法は計算効率が高いため、特に人気を集めています。しかし、これらの手法は典型的に 2 つの重要な制限を抱えています。すなわち、サンプル複雑度が劣っており O((n_1 + n_2)r^2) となること、そして
精度
\epsilon を達成するのに必要な反復回数の計算量が O(
a
\kappa
a \log(1/
\epsilon))
となり、目標行列が悪条件（ill-conditioned）であると収束が遅くなることです。ここで、\kappa は未知の行列の条件数（condition number）を表します。最近の研究では、GD の前処理付き変種である scaled gradient descent（ScaledGD）が、反復回数の計算量を O(
\log(1/
\epsilon)) に大幅に減らせることが示されています。それでもなお、そのサンプル複雑度は O((n_1 + n_2)r^2) と劣ったままです。これに対して、巧妙な仮想系列（virtual sequence）技術を用いると、正半定値（PSD）設定における標準的な GD が最適なサンプル複雑度 O((n_1 + n_2)r) を達成する一方、反復回数の計算量が O(
\kappa^2 \log(1/
\epsilon)) とより遅くなります。本論文では、より洗練された解析により、ScaledGD が最適なサンプル複雑度 O((n_1 + n_2)r) と改善された反復計算量 O(
\log(1/
\epsilon)) の両方を達成することを示します。特筆すべきは、我々の結果が PSD 設定を超えて、一般の低ランク行列回復問題にも拡張される点です。数値実験により、ScaledGD が悪条件な行列に対して最適なサンプリング複雑度を保ちながら収束を加速することがさらに検証されます。
