論文の概要: Efficiently Computing Sparse Fourier Transforms of $q$-ary Functions
- arxiv url: http://arxiv.org/abs/2301.06200v1
- Date: Sun, 15 Jan 2023 22:04:53 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-18 16:55:47.401525
- Title: Efficiently Computing Sparse Fourier Transforms of $q$-ary Functions
- Title(参考訳): q$-ary関数のスパースフーリエ変換の効率的な計算
- Authors: Yigit Efe Erginbas, Justin Singh Kang, Amirali Aghazadeh, Kannan
Ramchandran
- Abstract要約: 長さ$n$シーケンスの$q$-ary関数に特化してスパースフーリエ変換アルゴリズムを開発する。
固定$q$の場合、$q$-SFTのロバストバージョンはサンプル複雑性が$O(Sn2)$であり、計算複雑性が$O(Sn3)$と同じ保証を持つことを示す。
- 参考スコア(独自算出の注目度): 12.522202946750157
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Fourier transformations of pseudo-Boolean functions are popular tools for
analyzing functions of binary sequences. Real-world functions often have
structures that manifest in a sparse Fourier transform, and previous works have
shown that under the assumption of sparsity the transform can be computed
efficiently. But what if we want to compute the Fourier transform of functions
defined over a $q$-ary alphabet? These types of functions arise naturally in
many areas including biology. A typical workaround is to encode the $q$-ary
sequence in binary, however, this approach is computationally inefficient and
fundamentally incompatible with the existing sparse Fourier transform
techniques. Herein, we develop a sparse Fourier transform algorithm
specifically for $q$-ary functions of length $n$ sequences, dubbed $q$-SFT,
which provably computes an $S$-sparse transform with vanishing error as $q^n
\rightarrow \infty$ in $O(Sn)$ function evaluations and $O(S n^2 \log q)$
computations, where $S = q^{n\delta}$ for some $\delta < 1$. Under certain
assumptions, we show that for fixed $q$, a robust version of $q$-SFT has a
sample complexity of $O(Sn^2)$ and a computational complexity of $O(Sn^3)$ with
the same asymptotic guarantees. We present numerical simulations on synthetic
and real-world RNA data, demonstrating the scalability of $q$-SFT to massively
high dimensional $q$-ary functions.
- Abstract(参考訳): 擬ブール関数のフーリエ変換は二進列の関数を解析するための一般的なツールである。
実世界の函数はしばしば疎フーリエ変換に現れる構造を持ち、以前の研究はスパーシティの仮定の下で変換を効率的に計算できることを示した。
しかし、$q$-aryアルファベット上で定義される関数のフーリエ変換を計算したい場合はどうだろう?
このような機能は、生物学を含む多くの分野で自然に現れる。
典型的な回避策は、$q$-aryシーケンスをバイナリにエンコードすることであるが、このアプローチは計算効率が悪く、既存のスパースフーリエ変換技術と基本的に相容れない。
ここでは、長さ$n$列の$q$-ary関数に対して特別に$q$-ary関数に対して$q$-SFTというスパースフーリエ変換アルゴリズムを開発し、このアルゴリズムは、$q^n \rightarrow \infty$ in $O(Sn)$関数評価と$O(Sn^2 \log q)$演算と、$S = q^{n\delta}$ for some $\delta < 1$として証明的に$S$-sparse変換を演算する。
ある仮定の下では、固定$q$の場合、$q$-SFTのロバストバージョンはサンプル複雑性が$O(Sn^2)$であり、計算複雑性が$O(Sn^3)$で同じ漸近的保証を持つことを示す。
合成および実世界のRNAデータに対する数値シミュレーションを行い、超高次元の$q$-ary関数に対する$q$-SFTのスケーラビリティを示す。
関連論文リスト
- Adaptive approximation of monotone functions [0.0]
GreedyBox が任意の関数 $f$ に対して,対数因子まで,最適なサンプル複雑性を実現することを証明した。
おそらく予想通り、GreedyBoxの$Lp(mu)$エラーは、アルゴリズムによって予測されるよりもはるかに高速な$C2$関数で減少する。
論文 参考訳(メタデータ) (2023-09-14T08:56:31Z) - An Optimal Stochastic Algorithm for Decentralized Nonconvex Finite-sum
Optimization [25.21457349137344]
私たちは、DEARESTが少なくとも$mathcal O(+sqrtmnLvarepsilon-2)$ 1次オラクル(IFO)コールと$mathcal O(Lvarepsilon-2/sqrt1-lambda_W)$通信ラウンドを必要とすることを示す証拠を示します。
論文 参考訳(メタデータ) (2022-10-25T11:37:11Z) - Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。
我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
論文 参考訳(メタデータ) (2022-03-18T18:50:52Z) - Low-degree learning and the metric entropy of polynomials [49.1574468325115]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳(メタデータ) (2022-03-17T23:52:08Z) - 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) - Learning Set Functions that are Sparse in Non-Orthogonal Fourier Bases [73.53227696624306]
フーリエスパース集合関数を学習するための新しいアルゴリズム群を提案する。
Walsh-Hadamard変換に焦点をあてた他の研究とは対照的に、我々の新しいアルゴリズムは最近導入された非直交フーリエ変換で機能する。
いくつかの実世界のアプリケーションで有効性を示す。
論文 参考訳(メタデータ) (2020-10-01T14:31:59Z) - Convergence of Sparse Variational Inference in Gaussian Processes
Regression [29.636483122130027]
計算コストが$mathcalO(log N)2D(log N)2)$の手法を推論に利用できることを示す。
論文 参考訳(メタデータ) (2020-08-01T19:23:34Z) - Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation [30.137884459159107]
連続状態と行動空間を用いた強化学習において,Q$関数を効率よく学習する方法を考える。
我々は、$epsilon$-Schmidt $Q$-functionと$widetildeO(frac1epsilonmax(d1, d_2)+2)$のサンプル複雑性を求める単純な反復学習アルゴリズムを開発する。
論文 参考訳(メタデータ) (2020-06-11T00:55:35Z) - Quantum Legendre-Fenchel Transform [6.643082745560234]
離散ルジャンドル・フェンシェル変換を計算する量子アルゴリズムを提案する。
量子アルゴリズムは多対数因子に最適であることを示す。
論文 参考訳(メタデータ) (2020-06-08T18:00:05Z) - A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。
我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。
次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
論文 参考訳(メタデータ) (2020-06-02T16:38:36Z) - On the Modularity of Hypernetworks [103.1147622394852]
構造化対象関数の場合、ハイパーネットワークにおけるトレーニング可能なパラメータの総数は、標準ニューラルネットワークのトレーニング可能なパラメータの数や埋め込み法よりも桁違いに小さいことを示す。
論文 参考訳(メタデータ) (2020-02-23T22:51:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。