論文の概要: "Sliced" Subwindow Search: a Sublinear-complexity Solution to the Maximum Rectangle Problem

• arxiv url: http://arxiv.org/abs/1908.00140v2
• Date: Sun, 9 Apr 2023 21:48:47 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-12 01:11:49.907312
• Title: "Sliced" Subwindow Search: a Sublinear-complexity Solution to the Maximum Rectangle Problem
• Title（参考訳）: Sliced"サブウィンドウサーチ:最大矩形問題に対するサブ線形複雑解法
• Authors: Max Reuter, Gheorghe-Teodor Bercea, Liana Fong
• Abstract要約: 本稿では,行列の少数の等距離区間間を補間することにより,線形時間とメモリの複雑さを補間する問題に対する新しいアプローチを提案する。 提案手法は,11倍の高速化とメモリ効率を99%の精度で達成し,最先端技術よりも優れていた。 リアルタイムアプリケーションや、最大矩形問題の様々な計算困難インスタンスに適している。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Considering a 2D matrix of positive and negative numbers, how might one draw a rectangle within it whose contents sum higher than all other rectangles'? This fundamental problem, commonly known the maximum rectangle problem or subwindow search, spans many computational domains. Yet, the problem has not been solved without demanding computational resources at least linearly proportional to the size of the matrix. In this work, we present a new approach to the problem which achieves sublinear time and memory complexities by interpolating between a small amount of equidistant sections of the matrix. Applied to natural images, our solution outperforms the state-of-the-art by achieving an 11x increase in speed and memory efficiency at 99% comparative accuracy. In general, our solution outperforms existing solutions when matrices are sufficiently large and a marginal decrease in accuracy is acceptable, such as in many problems involving natural images. As such, it is well-suited for real-time application and in a variety of computationally hard instances of the maximum rectangle problem.
• Abstract（参考訳）: 正と負の数の2次元行列を考えると、その中身が他のすべての矩形よりも高い長方形を描くことができるのだろうか? この基本的な問題は、一般に最大長方形問題またはサブウィンドウ探索と呼ばれ、多くの計算領域にまたがる。 しかし、この問題は、行列のサイズに少なくとも線形に比例する計算資源を要求することなく解決されていない。 本研究では,行列の少数の等距離区間間を補間することにより,線形時間とメモリの複雑さを補間する問題に対する新しいアプローチを提案する。 自然画像に適用すると,11倍の速度とメモリ効率を99%の精度で達成し,最先端技術よりも優れる。 一般に,本手法は,行列が十分に大きく,精度の限界低下が許容される場合,例えば自然画像を含む多くの問題において,既存の解よりも優れる。 このように、リアルタイムアプリケーションや、最大矩形問題の様々な計算困難インスタンスに適している。

関連論文リスト

• Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization [26.36906884097317]
  我々は,リプシッツ,凸関数を次数次オラクルで最小化するための新しい並列アルゴリズムを開発した。 その結果,最もよく知られた問合せ深度と並列アルゴリズムの最もよく知られた計算深度とのギャップを埋めることができた。
  論文  参考訳（メタデータ） (2024-06-11T15:41:48Z)
• PoseGravity: Pose Estimation from Points and Lines with Axis Prior [3.5687541347524245]
  本稿では,カメラの回転行列の軸が与えられた絶対的なカメラポーズを推定するアルゴリズムを提案する。 この問題はハイパーボラと単位円の交点を見つけることで効率よく解ける。
  論文  参考訳（メタデータ） (2024-05-21T09:55:56Z)
• Multiple Convex Objects Image Segmentation via Proximal Alternating Direction Method of Multipliers [2.294014185517203]
  前述した凸形状は、各対象に関連付けられた二項指示関数上の単純な二次不等式制約であることが判明した。 凸形状を予め確率ベースに組み込んだ画像分割モデルを提案する。 自然画像と医用画像の数値実験により,提案手法は既存の方法よりも優れていることが示された。
  論文  参考訳（メタデータ） (2022-03-22T00:05:19Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  共分散行列の明示的な構成を避ける新しい推論手法を提案する。 本手法では, 数値線形代数と共役勾配アルゴリズムの対角線推定結果とを結合する。 いくつかのシミュレーションにおいて,本手法は計算時間とメモリにおける既存手法よりも拡張性が高い。
  論文  参考訳（メタデータ） (2022-02-25T16:35:26Z)
• Efficient Large Scale Inlier Voting for Geometric Vision Problems [3.1231364554255636]
  コンピュータビジョンにおける多くの応用において、アウター・リジェクション(英語版)と等価に不整集合最適化(英語版)が重要な要素である。 我々は、$Rd$の「交差」$k$次元曲面に基づいて、外周拒絶に対する効率的で一般的なアルゴリズムを提案する。 本手法は, 複数枚のカメラにおいて, 多数の一致が低い不整合比で発生する問題に対するアプローチの汎用性を示す。
  論文  参考訳（メタデータ） (2021-07-25T14:13:07Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。 我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。 標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
  論文  参考訳（メタデータ） (2021-07-09T16:04:24Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  非PSDおよび2乗根行列の次元削減法を提案する。 複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2021-06-16T04:07:48Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。 まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。 次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-01-19T04:24:23Z)
• Matrix-wise $\ell_0$-constrained Sparse Nonnegative Least Squares [22.679160149512377]
  多重右辺 (MNNLS) を持つ非負の最小二乗問題は、加法線形結合に依存するモデルに現れる。 本稿では,行列幅制約を用いたスパースMNNLSの新しい定式化を提案する。 提案した2段階の手法は,カラムワイドおよびグローバルの両方に適用された最先端のスパース符号よりも精度の高い結果が得られることを示す。
  論文  参考訳（メタデータ） (2020-11-22T17:21:16Z)
• Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations [59.84561168501493]
  最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。 驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。 提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
  論文  参考訳（メタデータ） (2020-08-12T08:52:50Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。