論文の概要: A Constrained BA Algorithm for Rate-Distortion and Distortion-Rate
Functions
- arxiv url: http://arxiv.org/abs/2305.02650v2
- Date: Thu, 18 Jan 2024 09:25:44 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-19 20:43:10.167383
- Title: A Constrained BA Algorithm for Rate-Distortion and Distortion-Rate
Functions
- Title（参考訳）: 速度歪みと歪み率関数に対する制約付きBAアルゴリズム
- Authors: Lingyi Chen, Shitong Wu, Wenhao Ye, Huihui Wu, Wenyi Zhang, Hao Wu and
Bo Bai
- Abstract要約: 速度歪み関数に対するBlahut-Arimoto (BA)アルゴリズムの修正
修正アルゴリズムは、与えられた対象歪みに対してRD関数を直接計算する。
- 参考スコア（独自算出の注目度）: 13.570794979535934
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Blahut-Arimoto (BA) algorithm has played a fundamental role in the
numerical computation of rate-distortion (RD) functions. This algorithm
possesses a desirable monotonic convergence property by alternatively
minimizing its Lagrangian with a fixed multiplier. In this paper, we propose a
novel modification of the BA algorithm, wherein the multiplier is updated
through a one-dimensional root-finding step using a monotonic univariate
function, efficiently implemented by Newton's method in each iteration.
Consequently, the modified algorithm directly computes the RD function for a
given target distortion, without exploring the entire RD curve as in the
original BA algorithm. Moreover, this modification presents a versatile
framework, applicable to a wide range of problems, including the computation of
distortion-rate (DR) functions. Theoretical analysis shows that the outputs of
the modified algorithms still converge to the solutions of the RD and DR
functions with rate $O(1/n)$, where $n$ is the number of iterations.
Additionally, these algorithms provide $\varepsilon$-approximation solutions
with $O\left(\frac{MN\log N}{\varepsilon}(1+\log |\log \varepsilon|)\right)$
arithmetic operations, where $M,N$ are the sizes of source and reproduced
alphabets respectively. Numerical experiments demonstrate that the modified
algorithms exhibit significant acceleration compared with the original BA
algorithms and showcase commendable performance across classical source
distributions such as discretized Gaussian, Laplacian and uniform sources.
- Abstract（参考訳）: Blahut-Arimoto(BA)アルゴリズムは、RD関数の数値計算において基本的な役割を担っている。
このアルゴリズムは、固定乗数でラグランジアンを最小化することで、望ましい単調収束性を持つ。
本稿では,単調な単変量関数を用いて1次元のルートフィニングステップを通じて乗算器を更新し,ニュートン法により各反復で効率よく実装したBAアルゴリズムの新たな改良を提案する。
これにより、修正アルゴリズムは、元のBAアルゴリズムのようにRD曲線全体を探索することなく、所定の対象歪みに対してRD関数を直接計算する。
さらに、この修正は、歪み率(DR)関数の計算を含む幅広い問題に適用可能な、汎用的なフレームワークを提供する。
理論的解析によると、修正アルゴリズムの出力はRD関数とDR関数の解になお収束し、レートは$O(1/n)$で、$n$は反復数である。
さらに、これらのアルゴリズムは$O\left(\frac{MN\log N}{\varepsilon}(1+\log |\log \varepsilon|)\right)$算術演算を伴う$\varepsilon$-approximationソリューションを提供する。
数値実験により、修正されたアルゴリズムは元のbaアルゴリズムと比較して大きな加速を示し、離散ガウス、ラプラシアン、一様ソースのような古典的ソース分布をまたいだ可換性能を示す。
関連論文リスト
- Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳（メタデータ） (2023-10-18T10:29:58Z) - Gradient-free optimization of highly smooth functions: improved analysis
and a new algorithm [87.22224691317766]
この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。
ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
論文 参考訳（メタデータ） (2023-06-03T17:05:13Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Alternatives to a nonhomogeneous partial differential equation quantum
algorithm [52.77024349608834]
Apsi(textbfr)=f(textbfr)$ という形の非等質線型偏微分方程式を解くための量子アルゴリズムを提案する。
これらの成果により、現代の技術に基づく量子アルゴリズムの実験的実装が容易になった。
論文 参考訳（メタデータ） (2022-05-11T14:29:39Z) - Alternating Mahalanobis Distance Minimization for Stable and Accurate CP
Decomposition [4.847980206213335]
本稿では, テンソルの特異値とベクトルを導出するための新しい定式化を導入する。
このアルゴリズムのサブスウィープは、既知のランクの正確なCPDに対して超線形収束率を達成することができることを示す。
すると、アルゴリズムは各因子に対するマハラノビス距離を最適化するものであり、基底距離は他の因子に依存していると見なす。
論文 参考訳（メタデータ） (2022-04-14T19:56:36Z) - A Fully Single Loop Algorithm for Bilevel Optimization without Hessian
Inverse [121.54116938140754]
両レベル最適化問題に対して,Hessian 逆フリーな完全単一ループアルゴリズムを提案する。
我々のアルゴリズムは$O(epsilon-2)$と収束することを示す。
論文 参考訳（メタデータ） (2021-12-09T02:27:52Z) - Faster First-Order Algorithms for Monotone Strongly DR-Submodular
Maximization [11.919431962501479]
連続部分モジュラ函数はDimishing Returns (DR) の性質を満たすが、これは非負の方向に沿って凹凸であることを意味する。
そこで本稿では,lceilfracLmurce$のあとで,証明可能な1-fracce$近似比と一致する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-11-15T18:53:14Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - A Domain-Shrinking based Bayesian Optimization Algorithm with
Order-Optimal Regret Performance [16.0251555430107]
これはGPに基づく最初のアルゴリズムであり、順序最適化された後悔の保証がある。
GP-UCB系のアルゴリズムと比較して,提案アルゴリズムは計算複雑性を$O(T2d-1)$で低減する。
論文 参考訳（メタデータ） (2020-10-27T02:15:15Z) - Provably Convergent Working Set Algorithm for Non-Convex Regularized
Regression [0.0]
本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。
その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
論文 参考訳（メタデータ） (2020-06-24T07:40:31Z) - Efficient algorithms for multivariate shape-constrained convex
regression problems [9.281671380673306]
最小二乗推定器は、制約付き凸プログラミング(QP)問題を$(n+1)d$変数と少なくとも$n(n-1)$線形不等式制約で解くことで計算可能であることを証明している。
一般に非常に大規模な凸QPを解くために、我々は2つの効率的なアルゴリズムを設計する。1つは対称ガウス・シーデルに基づく乗算器の交互方向法(tt sGS-ADMM)であり、もう1つは半滑らかニュートン法(tt)によって解かれる部分プロブレムを持つ近似拡張ラグランジアン法(tt pALM)である。
論文 参考訳（メタデータ） (2020-02-26T11:18:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。