Fugu-MT 論文翻訳(概要): On Outer Bi-Lipschitz Extensions of Linear Johnson-Lindenstrauss Embeddings of Low-Dimensional Submanifolds of $\mathbb{R}^N$

論文の概要: On Outer Bi-Lipschitz Extensions of Linear Johnson-Lindenstrauss Embeddings of Low-Dimensional Submanifolds of $\mathbb{R}^N$

arxiv url: http://arxiv.org/abs/2206.03376v1
Date: Tue, 7 Jun 2022 15:10:46 GMT
ステータス: 処理完了
システム内更新日: 2022-06-08 16:48:13.449186
Title: On Outer Bi-Lipschitz Extensions of Linear Johnson-Lindenstrauss Embeddings of Low-Dimensional Submanifolds of $\mathbb{R}^N$
Title（参考訳）: $\mathbb{R}^N$の低次元部分多様体の線形ジョンソン-リンデンシュトラウス埋め込みの外部ビプシッツ拡大について
Authors: Mark A. Iwen, Mark Philip Roach
Abstract要約: $mathcalM$ を $mathbbRN$ のコンパクト $d$-次元部分多様体とし、リーチ $tau$ とボリューム $V_mathcal M$ とする。非線形関数 $f: mathbbRN rightarrow mathbbRmm が存在し、$m leq C left(d / epsilon2right) log left(fracsqrt[d]V_math が存在することを証明します。
参考スコア（独自算出の注目度）: 0.24366811507669117
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Let $\mathcal{M}$ be a compact $d$-dimensional submanifold of $\mathbb{R}^N$ with reach $\tau$ and volume $V_{\mathcal M}$. Fix $\epsilon \in (0,1)$. In this paper we prove that a nonlinear function $f: \mathbb{R}^N \rightarrow \mathbb{R}^{m}$ exists with $m \leq C \left(d / \epsilon^2 \right) \log \left(\frac{\sqrt[d]{V_{\mathcal M}}}{\tau} \right)$ such that $$(1 - \epsilon) \| {\bf x} - {\bf y} \|_2 \leq \left\| f({\bf x}) - f({\bf y}) \right\|_2 \leq (1 + \epsilon) \| {\bf x} - {\bf y} \|_2$$ holds for all ${\bf x} \in \mathcal{M}$ and ${\bf y} \in \mathbb{R}^N$. In effect, $f$ not only serves as a bi-Lipschitz function from $\mathcal{M}$ into $\mathbb{R}^{m}$ with bi-Lipschitz constants close to one, but also approximately preserves all distances from points not in $\mathcal{M}$ to all points in $\mathcal{M}$ in its image. Furthermore, the proof is constructive and yields an algorithm which works well in practice. In particular, it is empirically demonstrated herein that such nonlinear functions allow for more accurate compressive nearest neighbor classification than standard linear Johnson-Lindenstrauss embeddings do in practice.
Abstract（参考訳）: $\mathcal{m}$ を$\mathbb{r}^n$ のコンパクトな $d$-次元部分多様体とし、$\tau$ と volume $v_{\mathcal m}$ に達する。 epsilon \in (0,1)$ を修正します。本稿では、非線形関数 $f: \mathbb{r}^n \rightarrow \mathbb{r}^{m}$ が $m \leq c \left(d / \epsilon^2 \right) \log \left(\frac{\sqrt[d]{v_{\mathcal m}}}{\tau} \right)$ で$(1 - \epsilon) \| {\bf x} - {\bf y} \|_2 \leq \left\| f({\bf x}) - f({\bf y}) \right\|_2 \leq (1 + \epsilon) \| {\bf x} - {\bf y} \|_2$$ となることを証明する。事実上、$f$は、$\mathcal{M}$ から $\mathbb{R}^{m}$ への双Lipschitz函数として機能するだけでなく、$\mathcal{M}$ に満たない点から$\mathcal{M}$ のすべての点までの距離をほぼ保存する。さらに、証明は構成的であり、実際にうまく動作するアルゴリズムが得られる。特に、このような非線形関数は標準線形ジョンソン・リンデンシュトラウス埋め込みよりもより正確な圧縮的近接分類を可能にすることが実証的に証明されている。

関連論文リスト

The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文参考訳（メタデータ） (2024-10-26T06:21:42Z)
A class of ternary codes with few weights [0.0]
本稿では,$mathcalC$ := (textTr) := (textTr(dx), dots, dots, d_n$で定義される3次コード$mathcalC$ of length $n$について検討する。指数和の明示的な評価に関する最近の結果を用いて、Weil境界とテクニックを判定し、$mathcalC$の双対符号がハミング境界に対して最適であることを示す。
論文参考訳（メタデータ） (2024-10-05T16:15:50Z)
Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文参考訳（メタデータ） (2024-06-07T08:26:31Z)
Noncompact uniform universal approximation [0.0]
普遍近似定理は、(コンパクトでない)入力空間 $mathbbRn$ 上の一様収束に一般化される。無限大で消えるすべての連続関数は、ニューラルネットワークによって一様に近似することができる。
論文参考訳（メタデータ） (2023-08-07T08:54:21Z)
Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。目標は、低ランク因子の積として$mathbfA$を近似することである。我々の手法はBMF問題の他の一般的な変種に一般化する。
論文参考訳（メタデータ） (2023-06-02T18:55:27Z)
Online Learning of Smooth Functions [0.35534933448684125]
隠れ関数が一定の滑らか性を持つことが知られている実数値関数のオンライン学習について検討する。定数係数までシャープな$textopt_p(mathcal F_q)$の新たなバウンダリを見つける。マルチ変数のセットアップでは、$textopt_p(mathcal F_q,d)$ to $textopt_p(mathcal F_q,d)$に関連する不等式を確立し、$textopt_p(mathcal F)$を示す。
論文参考訳（メタデータ） (2023-01-04T04:05:58Z)
Convergence Rates of Stochastic Zeroth-order Gradient Descent for \L ojasiewicz Functions [6.137707924685666]
Lojasiewicz関数に対するゼロ階勾配 Descent (SZGD) アルゴリズムの収束率を証明する。その結果, mathbbN $ における f (mathbfx_t) - f (mathbfx_infty) _t は $ | mathbfx_infty よりも早く収束できることがわかった。
論文参考訳（メタデータ） (2022-10-31T00:53:17Z)
Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文参考訳（メタデータ） (2022-06-17T17:55:43Z)
Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文参考訳（メタデータ） (2022-02-10T16:10:41Z)
Linear Bandits on Uniformly Convex Sets [88.3673525964507]
線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。 2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
論文参考訳（メタデータ） (2021-03-10T07:33:03Z)
A Canonical Transform for Strengthening the Local $L^p$-Type Universal Approximation Property [4.18804572788063]
任意の機械学習モデルクラス $mathscrFsubseteq C(mathbbRd,mathbbRD)$ が $Lp_mu(mathbbRd,mathbbRD)$ で密であることを保証する。本稿では、「$mathscrF$'s approximation property」という正準変換を導入することにより、この近似理論問題に対する一般的な解を提案する。
論文参考訳（メタデータ） (2020-06-24T17:46:35Z)

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

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