抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
有界エントリ(||A|||1)を持つ行列A>Rn×nが,PSD円錐からのユークリッド距離における正の半定値(PSD),またはε-farであるかどうかの試験の問題を研究し,Bsucceq0がBがPSDであると示す,min_Bsucceq0′′A-B′′_F2||n2であることを意味した。著者らの主なアルゴリズム的貢献は,O(1/ε4)クエリだけを用いて,A.11Thoughoutの入力にO(1/ε4)クエリーを用いて区別する非適応テスターであり,O(.)hidelog(1/ε)因子であった。Euclidianノルムの代わりに,スペクトルノルムの距離を考慮して,著者らは,AがPSDか,または,min_Bsucc0′′A-B′′_2||nを満足する”l_∞ギャップ問題”を得た。この関連問題に対して,筆者らは,O(1/ε2)クエリテスターを与え,それはlog(1/ε)因子まで最適であることを示した。両テスターは,無作為に主要なサブマトリクスの収集をサンプリングし,これらのサブマトリックスがPSDであるかどうかをチェックする。順次,このアルゴリズムは,AがPSDでないときに,Aが負の固有値を持つ証明書を返すという一面誤差を達成した。任意の非適応アルゴリズムに対してΩ(1/ε2)下限を与えることにより,Euclidianノルム距離によるPSD試験に対する上限を補完した。この下限構築は一般的であり,多くのスペクトル試験問題に対する下限を導くために使用できる。著者らの構築の適用性の例として,著者らは,Balcan,Li,Woodruff,およびZhang[11]の結果を拡張する,ε_n1.5ギャップを有するSchatten-1ノルムをテストするために,新しいΩ(1/ε4)サンプリング下限を得た。さらに,著者らのハードインスタンスは,Ky-Fan Normを推定するための新しいサンプリング下限と,ランク-k近似のコスト,すなわち,||A-A_k||_F2=Σ_i>kσ_i2(A)のコストをもたらした。Copyright 2021 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】
