論文の概要: On Fast Johnson-Lindernstrauss Embeddings of Compact Submanifolds of
$\mathbb{R}^N$ with Boundary
- arxiv url: http://arxiv.org/abs/2110.04193v1
- Date: Fri, 8 Oct 2021 15:27:52 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-11 16:50:00.993168
- Title: On Fast Johnson-Lindernstrauss Embeddings of Compact Submanifolds of
$\mathbb{R}^N$ with Boundary
- Title（参考訳）: 境界を持つ$\mathbb{r}^n$のコンパクト部分多様体の高速ジョンソン・リンダーンシュトラウス埋め込みについて
- Authors: Mark A. Iwen, Benjamin Schmidt, Arman Tavakoli
- Abstract要約: mathbbRm × N$ のランダム行列 $A がバイリプシッツ函数 $A: MathcalM rightarrow mathbbRm$ とビリプシッツ定数が 1 に近い確率を考える。
我々は、$mathbbRN$ の十分低次元部分多様体を埋め込むための、高度に構造化された分布の新しいクラスを示す。
- 参考スコア（独自算出の注目度）: 0.4125187280299246
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Let $\mathcal{M}$ be a smooth $d$-dimensional submanifold of $\mathbb{R}^N$
with boundary that's equipped with the Euclidean (chordal) metric, and choose
$m \leq N$. In this paper we consider the probability that a random matrix $A
\in \mathbb{R}^{m \times N}$ will serve as a bi-Lipschitz function $A:
\mathcal{M} \rightarrow \mathbb{R}^m$ with bi-Lipschitz constants close to one
for three different types of distributions on the $m \times N$ matrices $A$,
including two whose realizations are guaranteed to have fast matrix-vector
multiplies. In doing so we generalize prior randomized metric space embedding
results of this type for submanifolds of $\mathbb{R}^N$ by allowing for the
presence of boundary while also retaining, and in some cases improving, prior
lower bounds on the achievable embedding dimensions $m$ for which one can
expect small distortion with high probability. In particular, motivated by
recent modewise embedding constructions for tensor data, herein we present a
new class of highly structured distributions on matrices which outperform prior
structured matrix distributions for embedding sufficiently low-dimensional
submanifolds of $\mathbb{R}^N$ (with $d \lesssim \sqrt{N}$) with respect to
both achievable embedding dimension, and computationally efficient
realizations. As a consequence we are able to present, for example, a general
new class of Johnson-Lindenstrauss embedding matrices for $\mathcal{O}(\log^c
N)$-dimensional submanifolds of $\mathbb{R}^N$ which enjoy $\mathcal{O}(N \log
\log N))$-time matrix vector multiplications.
- Abstract（参考訳）: $\mathcal{m}$ を、ユークリッド(弦)計量を備えた境界を持つ$\mathbb{r}^n$ の滑らかな $d$-次元部分多様体とし、$m \leq n$ を選択する。
本稿では、ランダム行列 $A \in \mathbb{R}^{m \times N}$ が双Lipschitz函数 $A: \mathcal{M} \rightarrow \mathbb{R}^m$ として作用する確率を考える。
このようにして、このタイプのサブ多様体に対する事前ランダム化計量空間の埋め込み結果を$\mathbb{R}^N$ として一般化し、境界の存在を保ちながら維持し、場合によっては達成可能な埋め込み次元の下位境界を $m$ とすることで、高い確率で小さな歪みを期待できる。
特に、テンソルデータに対する最近のモードワイズ埋め込み構造によって動機付けられ、ここでは、達成可能な埋め込み次元と計算効率の両面に関して、$\mathbb{R}^N$($d \lesssim \sqrt{N}$)の十分低次元部分多様体を埋め込むための事前構造化行列分布より優れた行列上の高度構造化分布のクラスを示す。
結果として、例えば、johnson-lindenstrauss埋め込み行列の一般的な新しいクラスを、$\mathcal{o}(\log^c n)$-dimensional submanifolds of $\mathbb{r}^n$ で表すことができ、$\mathcal{o}(n \log \log n))$-time matrix vector multiplication が楽しめる。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - 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) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - 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) - Spectrum of inner-product kernel matrices in the polynomial regime and
multiple descent phenomenon in kernel ridge regression [3.997680012976965]
カーネル行列はその次数-$ell$近似によってよく近似される。
行列のスペクトルが分布に収束することを示す。
論文 参考訳（メタデータ） (2022-04-21T22:20:52Z) - Beyond Independent Measurements: General Compressed Sensing with GNN
Application [4.924126492174801]
我々は、ノイズコーン観測からmathbbRn$の構造化信号$mathbfxを復元する問題を考察する。
実効的な$mathbfB$は測定値のサロゲートとして用いられる可能性がある。
論文 参考訳（メタデータ） (2021-10-30T20:35:56Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳（メタデータ） (2021-10-05T09:33:49Z) - Spectral properties of sample covariance matrices arising from random
matrices with independent non identically distributed columns [50.053491972003656]
関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$.
ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
論文 参考訳（メタデータ） (2021-09-06T14:21:43Z) - Algebraic and geometric structures inside the Birkhoff polytope [0.0]
Birkhoff polytope $mathcalB_d$ は位数 $d$ のすべての双確率行列からなる。
我々は、$mathcalL_d$ と $mathcalF_d$ が平面行列に対して星型であることを証明する。
論文 参考訳（メタデータ） (2021-01-27T09:51:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。