論文の概要: 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のスケーラビリティを示す。
関連論文リスト
- Approximation Rates for Shallow ReLU$^k$ Neural Networks on Sobolev Spaces via the Radon Transform [4.096453902709292]
我々は,ReLU$k$アクティベーション関数がソボレフ空間からの関数をいかに効率的に近似できるかという問題を考察する。
例えば、$qleq p$, $pgeq 2$, $s leq k + (d+1)/2$ などである。
論文 参考訳（メタデータ） (2024-08-20T16:43:45Z) - Fast Fourier transforms and fast Wigner and Weyl functions in large quantum systems [0.0]
高速フーリエ変換の2つの方法が量子文脈で用いられる。
最初の方法はヒルベルト空間$D=dn$と奇数整数$d$の次元を持つ系に対するものである。
第二の方法は、ヒルベルト空間の大きい有限次元の量子系において、ウィグナー函数とワイル函数の高速計算にも用いられる。
論文 参考訳（メタデータ） (2024-05-08T15:54:35Z) - Learning to Understand: Identifying Interactions via the Möbius Transform [18.987216240237483]
学習関数の解釈可能な表現を見つけるために、M"obius transform を用いる。
このアルゴリズムの頑健なバージョンはノイズに耐え、この複雑さを維持する。
いくつかの例では、M"obius変換によって生成される表現は元の関数に最大で2倍忠実である。
論文 参考訳（メタデータ） (2024-02-04T22:47:34Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。
我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
論文 参考訳（メタデータ） (2022-03-18T18:50:52Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。