論文の概要: Lattice partition recovery with dyadic CART
- arxiv url: http://arxiv.org/abs/2105.13504v1
- Date: Thu, 27 May 2021 23:41:01 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-31 13:46:57.395359
- Title: Lattice partition recovery with dyadic CART
- Title（参考訳）: Dyadic CARTによる格子分割回復
- Authors: Oscar Hernan Madrid Padilla, Yi Yu, Alessandro Rinaldo
- Abstract要約: 我々は、$d$次元格子上の加法ガウス雑音によって破損したピースワイド定値信号について検討する。
この形式のデータは、多くのアプリケーションで自然に発生し、統計処理や信号処理の文献において、信号の検出やテスト、ノイズの除去、推定といったタスクが広く研究されている。
本稿では,未知の信号の一貫性領域によって誘導される格子の分割を推定する,分割回復の問題について考察する。
我々は、DCARTベースの手順が、下位分割を$sigma2 k*の順序で一貫して推定することを証明した。
- 参考スコア（独自算出の注目度）: 79.96359947166592
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study piece-wise constant signals corrupted by additive Gaussian noise
over a $d$-dimensional lattice. Data of this form naturally arise in a host of
applications, and the tasks of signal detection or testing, de-noising and
estimation have been studied extensively in the statistical and signal
processing literature. In this paper we consider instead the problem of
partition recovery, i.e.~of estimating the partition of the lattice induced by
the constancy regions of the unknown signal, using the
computationally-efficient dyadic classification and regression tree (DCART)
methodology proposed by \citep{donoho1997cart}. We prove that, under
appropriate regularity conditions on the shape of the partition elements, a
DCART-based procedure consistently estimates the underlying partition at a rate
of order $\sigma^2 k^* \log (N)/\kappa^2$, where $k^*$ is the minimal number of
rectangular sub-graphs obtained using recursive dyadic partitions supporting
the signal partition, $\sigma^2$ is the noise variance, $\kappa$ is the minimal
magnitude of the signal difference among contiguous elements of the partition
and $N$ is the size of the lattice. Furthermore, under stronger assumptions,
our method attains a sharper estimation error of order
$\sigma^2\log(N)/\kappa^2$, independent of $ k^*$, which we show to be minimax
rate optimal. Our theoretical guarantees further extend to the partition
estimator based on the optimal regression tree estimator (ORT) of
\cite{chatterjee2019adaptive} and to the one obtained through an NP-hard
exhaustive search method. We corroborate our theoretical findings and the
effectiveness of DCART for partition recovery in simulations.
- Abstract（参考訳）: 我々は,d$次元格子上のガウス雑音により分解された断片的定数信号について検討する。
この形式のデータは、自然に多くのアプリケーションで発生し、信号検出やテスト、脱ノイズ、推定のタスクは、統計学や信号処理の文献で広く研究されている。
本稿では, 分割回復問題, すなわち, 未知信号の連続領域によって誘導される格子の分割を, \citep{donoho 1997cart} が提唱した計算効率の良いダイアディック分類と回帰木(DCART)手法を用いて推定する。
We prove that, under appropriate regularity conditions on the shape of the partition elements, a DCART-based procedure consistently estimates the underlying partition at a rate of order $\sigma^2 k^* \log (N)/\kappa^2$, where $k^*$ is the minimal number of rectangular sub-graphs obtained using recursive dyadic partitions supporting the signal partition, $\sigma^2$ is the noise variance, $\kappa$ is the minimal magnitude of the signal difference among contiguous elements of the partition and $N$ is the size of the lattice.
さらに、より強い仮定の下では、最小値が最適であることを示すk^*$とは独立に、位数$\sigma^2\log(N)/\kappa^2$のよりシャープな推定誤差が得られる。
この理論的な保証は, <cite{chatterjee2019adaptive} の最適回帰木推定器 (ort) とnp-hard exhaustive search 法による分割推定器 (partition estimator) にさらに拡張される。
シミュレーションにおける分割回復におけるDCARTの有効性と理論的知見の相関について検討した。
関連論文リスト
- Estimating Higher-Order Mixed Memberships via the $\ell_{2,\infty}$
Tensor Perturbation Bound [8.521132000449766]
テンソルブロックモデルの一般化であるテンソル混合メンバーシップブロックモデルを提案する。
我々は,モデルの同定可能性を確立し,計算効率の良い推定手法を提案する。
本手法を実データおよびシミュレーションデータに適用し,個別のコミュニティメンバーシップを持つモデルから特定できない効果を示す。
論文 参考訳（メタデータ） (2022-12-16T18:32:20Z) - Subspace clustering in high-dimensions: Phase transitions \&
Statistical-to-Computational gap [24.073221004661427]
部分空間クラスタリングを研究するための単純なモデルは、高次元の$k$-ガウス混合モデルである。
広帯域な高次元状態における統計的に最適な再構成誤差を正確に評価する。
論文 参考訳（メタデータ） (2022-05-26T17:47:35Z) - Selective Multiple Power Iteration: from Tensor PCA to gradient-based
exploration of landscapes [7.648784748888189]
Selective Multiple Power Iterations (SMPI) はスパイクを回復する重要な問題に対処する新しいアルゴリズムである。
これらの予期せぬ性能は、ノイズが信号の回復に重要な役割を果たす強力なメカニズムに起因していることを示す。
これらの結果は、実用的および理論的応用の両方に強い影響を与える可能性がある。
論文 参考訳（メタデータ） (2021-12-23T01:46:41Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳（メタデータ） (2021-09-24T14:48:20Z) - Generalized Orthogonal Procrustes Problem under Arbitrary Adversaries [1.0152838128195467]
半定値緩和法(SDR)と一般化パワー法(GPM)という反復法を用いて最小二乗推定値を求める。
さらに,低ランク因数分解アルゴリズムを解析し,対応する最適化環境が局所最小化器を含まないことを示す。
論文 参考訳（メタデータ） (2021-06-29T15:19:25Z) - Towards Sample-Optimal Compressive Phase Retrieval with Sparse and
Generative Priors [59.33977545294148]
O(k log L)$サンプルは振幅に基づく経験損失関数を最小化する任意のベクトルに信号が近いことを保証するのに十分であることを示す。
この結果はスパース位相検索に適応し、基底信号が$s$-sparseおよび$n$-dimensionalである場合、$O(s log n)$サンプルは同様の保証に十分であることを示す。
論文 参考訳（メタデータ） (2021-06-29T12:49:54Z) - Complexity of zigzag sampling algorithm for strongly log-concave
distributions [6.336005544376984]
強いログ凹分布に対するジグザグサンプリングアルゴリズムの計算複雑性について検討する。
ジグザグサンプリングアルゴリズムは, 計算コストが$obiglに匹敵するchi-squareの発散において, $varepsilon$ 誤差を達成することを証明した。
論文 参考訳（メタデータ） (2020-12-21T03:10:21Z) - Faster Convergence of Stochastic Gradient Langevin Dynamics for
Non-Log-Concave Sampling [110.88857917726276]
我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。
我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
論文 参考訳（メタデータ） (2020-10-19T15:23:18Z) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳（メタデータ） (2020-06-24T06:01:24Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。