抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
ストリーミング幾何学的データ解析のための多くの既存のアルゴリズムは,高次元データセットを処理するのに望ましくない空間複雑度における指数関数的依存性によって悩まされている。特に,一度d≧lognの場合,[AHV04]からストリーミング計算幾何学における長線の研究にもかかわらず,凸包とL”所有者-John楕円”を維持するような問題に対する既知の非自明なストリーミングアルゴリズムは存在しない。著者らは同時に,ポリ(d,logn)因子歪みによるトレードオフによって,空間のポリ(d,logn)ビットにこれらの結果を改善した。ポリ(d,logn)空間およびポリ(d,logn)歪みを有するl_∞部分空間埋込みのためのコアセットを維持するための最初のストリーミングアルゴリズムを設計することによって,これらの結果を統一的に達成した。また,このアルゴリズムは,オンラインコアセットモデルに類似の保証を与え,ログ条件数依存性をlogn依存性に置き換えることにより,オンライン数値線形代数に対する結果を鋭くし,[BDM+2]の質問に答えた。この技法は,レバレッジスコア,数値線形代数における基本的オブジェクト,およびl_p部分空間埋込みに対する計算幾何学の間の新しい接続を提供し,例えば,1パスストリーミングアルゴリズムに対する空間と歪みの間のほぼ最適なトレードオフを与え,p>2に対するO(d ̄2logn)空間とO((dlogn) ̄1/2-1/p)歪を用いて決定論的コアセットを与え,一方,以前の決定論的アルゴリズムは空間または歪[CDW18]においてポリ(n)因子を与えた。この技法はオフライン設定に意味があり,ここでは部分空間スケッチデータ構造の空間複雑性と歪みの間の最適トレードオフを与える。これを行うために,著者らは[LT80]の”密度”定理の基礎的証明を与えて,それをアルゴリズムにした。【JST・京大機械翻訳】
