論文の概要: Tight Bounds for Volumetric Spanners and Applications

• arxiv url: http://arxiv.org/abs/2310.00175v1
• Date: Fri, 29 Sep 2023 22:43:30 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-05 06:14:31.541984
• Title: Tight Bounds for Volumetric Spanners and Applications
• Title（参考訳）: ボリュームスパナ用タイトバウンドとその応用
• Authors: Aditya Bhaskara, Sepideh Mahabadi and Ali Vakilian
• Abstract要約: 興味のある点の集合が与えられたとき、スパンナーはすべての点を「小さい」係数で表現できる点の行列式である。 本稿では,すべての$ell_p$ベクトルに対して,スパンナーのサイズをほぼ最適に制限し,簡単な局所探索手法を用いて構築可能であることを示す。
• 参考スコア（独自算出の注目度）: 19.839528728535274
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given a set of points of interest, a volumetric spanner is a subset of the points using which all the points can be expressed using "small" coefficients (measured in an appropriate norm). Formally, given a set of vectors $X = \{v_1, v_2, \dots, v_n\}$, the goal is to find $T \subseteq [n]$ such that every $v \in X$ can be expressed as $\sum_{i\in T} \alpha_i v_i$, with $\|\alpha\|$ being small. This notion, which has also been referred to as a well-conditioned basis, has found several applications, including bandit linear optimization, determinant maximization, and matrix low rank approximation. In this paper, we give almost optimal bounds on the size of volumetric spanners for all $\ell_p$ norms, and show that they can be constructed using a simple local search procedure. We then show the applications of our result to other tasks and in particular the problem of finding coresets for the Minimum Volume Enclosing Ellipsoid (MVEE) problem.
• Abstract（参考訳）: 興味のある点の集合が与えられたとき、体積スパンナー(英: volumetric spanner)は、すべての点を「小さい」係数(適切なノルムで測る)で表現できる点の部分集合である。 形式的には、ベクトルの集合 $X = \{v_1, v_2, \dots, v_n\}$ が与えられたとき、ゴールは、すべての$v \in X$ が $\sum_{i\in T} \alpha_i v_i$ として表現できるような$T \subseteq [n]$ を見つけることである。 この概念は良く条件付けされた基底としても言及されており、バンディット線形最適化、行列行列行列最大化、行列低階近似などいくつかの応用がある。 本稿では,すべての$\ell_p$ノルムに対して,体積スパンナーのサイズをほぼ最適に制限し,簡単な局所探索法を用いて構築可能であることを示す。 次に、この結果の他のタスクへの応用、特に最小体積閉楕円体問題(MVEE)のコアセットを見つける問題を示す。

関連論文リスト

• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces [2.687607197645453]
  次元$Theta(log n)$ が $(sqrt3/2-o(1))$hard である場合でさえ、FPTアルゴリズムを近似する。 また、次元 $Theta(log n)$ が $(sqrt3/2-o(1))$hard であるような特別な場合でさえ、FPTアルゴリズムを近似することを示す。
  論文  参考訳（メタデータ） (2023-05-12T08:43:28Z)
• Learning linear dynamical systems under convex constraints [4.4351901934764975]
  線形力学系を単一軌道の$T$サンプルから同定する問題を考察する。 A*$は、制約のない設定に必要な値よりも$T$小さい値を確実に見積もることができる。
  論文  参考訳（メタデータ） (2023-03-27T11:49:40Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Towards Optimal Lower Bounds for k-median and k-means Coresets [25.713987341159918]
  計量空間における点の集合が与えられたとき、$(k,z)$-クラスタリング問題は、センターと呼ばれる点の集合を見つけることからなる。 我々は、$(k,z)$クラスタリングの任意のコアセットが、少なくとも$Omega(k varepsilon-2 log n)$と$Omega(k varepsilon-2 D)$ポイントでなければならないことを示す。
  論文  参考訳（メタデータ） (2022-02-25T16:13:28Z)
• On Complexity of 1-Center in Various Metrics [20.92192456060298]
  計量空間における集合 $P$ of $n$ が与えられたとき、$P$ の点を見つけると、他の点への最大距離が $P$ になる。 この問題の複雑さを$d$-dimensional $ell_p$-metricsと編集およびUlamメトリクスで調べる。
  論文  参考訳（メタデータ） (2021-12-06T18:25:11Z)
• The Power of Subsampling in Submodular Maximization [51.629656762796564]
  このアプローチは,既存の手法よりもはるかに単純であるにもかかわらず,最適/最先端の結果をもたらすことを示す。 我々は,映像要約,位置情報要約,映画推薦タスクにおけるアルゴリズムの有効性を実証的に示す。
  論文  参考訳（メタデータ） (2021-04-06T20:25:57Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• On Suboptimality of Least Squares with Application to Estimation of Convex Bodies [74.39616164169131]
  雑音支援関数の測定から得られる凸を次元$dgeq 6$で推定する際、最小広場の最適性に関するオープンな問題を解決した。 Least Squaresは準最適であり、$tildeTheta_d(n-2/(d-1))$であるのに対して、minimaxレートは$Theta_d(n-4/(d+3)$である。
  論文  参考訳（メタデータ） (2020-06-07T05:19:00Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。