論文の概要: Efficient Tensor Completion Algorithms for Highly Oscillatory Operators
- arxiv url: http://arxiv.org/abs/2510.17734v2
- Date: Tue, 21 Oct 2025 18:05:09 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-25 03:08:12.133519
- Title: Efficient Tensor Completion Algorithms for Highly Oscillatory Operators
- Title（参考訳）: 高振動演算子のための効率的なテンソル補完アルゴリズム
- Authors: Navjot Singh, Edgar Solomonik, Xiaoye Sherry Li, Yang Liu,
- Abstract要約: 本稿では,低複雑性テンソル補完アルゴリズムとその効率的な実装について述べる。
基礎となるテンソル分解は、入力行列とその蝶分解を位数$O(log n)$tensorに置き換えることに基づいている。
- 参考スコア（独自算出の注目度）: 7.563400478703737
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper presents low-complexity tensor completion algorithms and their efficient implementation to reconstruct highly oscillatory operators discretized as $n\times n$ matrices. The underlying tensor decomposition is based on the reshaping of the input matrix and its butterfly decomposition into an order $O (\log n)$ tensor. The reshaping of the input matrix into a tensor allows for representation of the butterfly decomposition as a tensor decomposition with dense tensors. This leads to efficient utilization of the existing software infrastructure for dense and sparse tensor computations. We propose two tensor completion algorithms in the butterfly format, using alternating least squares and gradient-based optimization, as well as a novel strategy that uses low-rank matrix completion to efficiently generate an initial guess for the proposed algorithms. To demonstrate the efficiency and applicability of our proposed algorithms, we perform three numerical experiments using simulated oscillatory operators in seismic applications. In these experiments, we use $O (n \log n)$ observed entries in the input matrix and demonstrate an $O(n\log^3 n)$ computational cost of the proposed algorithms, leading to a speedup of orders of magnitudes per iteration for large matrices compared to the low-rank matrix and quantized tensor-train completion. Moreover, the proposed butterfly completion algorithms, equipped with the novel initial guess generation strategy, achieve reconstruction errors that are smaller by an order of magnitude, enabling accurate recovery of the underlying structure compared to the state-of-the-art completion algorithms.
- Abstract（参考訳）: 本稿では,低複素性テンソル完備化アルゴリズムとその高振動演算子を$n\times n$行列として復号化するための効率的な実装について述べる。
基礎となるテンソル分解は、入力行列とその蝶分解を$O(\log n)$tensorに置き換えることに基づいている。
入力行列をテンソルに変換することにより、高密度テンソルを持つテンソル分解としてバタフライ分解を表現することができる。
これにより、既存のソフトウェアインフラを高密度かつスパースなテンソル計算に効率的に利用することができる。
本稿では,最小二乗と勾配に基づく最適化を交互に用い,バタフライ方式のテンソル補完アルゴリズムを2つ提案すると共に,低ランク行列補完を用いて提案アルゴリズムの初期推定を効率的に生成する新しい手法を提案する。
提案アルゴリズムの有効性と適用性を実証するために, シミュレーション振動子を用いた3つの数値実験を行った。
これらの実験では、入力行列に$O (n \log n)$の観測項目を用い、提案アルゴリズムの計算コストを$O(n\log^3 n)$で表し、低ランク行列と量子テンソルトレイン補完と比較して、大規模な行列に対して1イテレーションあたりのオーダーの高速化をもたらす。
さらに, 提案手法は, 新規な初期推測生成戦略を取り入れたバタフライ補完アルゴリズムを用いて, 精度の高い復元誤差を桁違いに小さくし, 現状の完成アルゴリズムと比較して, 基礎構造を正確に復元することを可能にする。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Tensor networks based quantum optimization algorithm [0.0]
最適化において、よく知られた古典的アルゴリズムの1つは電力反復である。
我々はこの落とし穴を回避するために量子化を提案する。
我々の手法はインスタンス非依存となり、量子コンピューティングの枠組みの中でブラックボックス最適化に対処することができる。
論文 参考訳（メタデータ） (2024-04-23T13:49:11Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳（メタデータ） (2023-10-18T10:29:58Z) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-30T15:57:14Z) - Latent Matrices for Tensor Network Decomposition and to Tensor
Completion [8.301418317685906]
テンソルを小さく分解し,アルゴリズムの計算を高速化する新しい高階テンソル分解モデルを提案する。
LMTN-PAM, LMTN-SVD, LMTN-ARの3つの最適化アルゴリズムを開発し, テンソル補完タスクに適用した。
実験の結果, LMTN-SVDアルゴリズムはFCTN-PAMアルゴリズムの3～6倍高速であり, 1.8ポイントの精度低下しか得られなかった。
論文 参考訳（メタデータ） (2022-10-07T08:19:50Z) - Softmax-free Linear Transformers [90.83157268265654]
視覚変換器(ViT)は、視覚知覚タスクの最先端を推し進めている。
既存の手法は理論的に欠陥があるか、視覚認識に経験的に効果がないかのいずれかである。
我々はSoftmax-Free Transformers (SOFT) のファミリーを提案する。
論文 参考訳（メタデータ） (2022-07-05T03:08:27Z) - Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via
GDPA Linearization [59.87663954467815]
アルゴリズムの展開は、モデルベースのアルゴリズムの各イテレーションをニューラルネットワーク層として実装することにより、解釈可能で類似のニューラルネットワークアーキテクチャを生成する。
本稿では、Gershgorin disc perfect alignment (GDPA)と呼ばれる最近の線形代数定理を利用して、二進グラフの半定値プログラミング緩和(SDR)のためのプロジェクションフリーアルゴリズムをアンロールする。
実験結果から,我々の未学習ネットワークは純粋モデルベースグラフ分類器よりも優れ,純粋データ駆動ネットワークに匹敵する性能を示したが,パラメータははるかに少なかった。
論文 参考訳（メタデータ） (2021-09-10T07:01:15Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - New Riemannian preconditioned algorithms for tensor completion via
polyadic decomposition [10.620193291237262]
これらのアルゴリズムは、ポリアジック分解形態におけるローランクテンソルの因子行列の積空間上の非ユークリッド計量を利用する。
提案された勾配降下アルゴリズムがテンソル完備問題の定常点にグローバルに収束することを証明する。
合成データと実世界のデータの数値計算結果から,提案アルゴリズムは最先端アルゴリズムよりもメモリと時間において効率的であることが示唆された。
論文 参考訳（メタデータ） (2021-01-26T22:11:06Z) - Alternating minimization algorithms for graph regularized tensor
completion [8.26185178671935]
我々は、低ランクテンソル完備化(LRTC)に対するカノニカルポリアディック(CP)分解法を考える。
グラフ正規化の使用にはLRTCの学習精度のメリットが伴うが、同時に結合グラフラプラシア語を誘導する。
基礎となるCP分解モデルにおけるブロック構造を利用して, 効率の良い同期最小化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-08-28T23:20:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。