論文の概要: Matrix-wise $\ell_0$-constrained Sparse Nonnegative Least Squares
- arxiv url: http://arxiv.org/abs/2011.11066v4
- Date: Wed, 22 Jun 2022 19:54:54 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-22 09:01:31.955385
- Title: Matrix-wise $\ell_0$-constrained Sparse Nonnegative Least Squares
- Title（参考訳）: 行列的に$\ell_0$-制約付きスパース非負極正方形
- Authors: Nicolas Nadisic, Jeremy E Cohen, Arnaud Vandaele, Nicolas Gillis
- Abstract要約: 多重右辺 (MNNLS) を持つ非負の最小二乗問題は、加法線形結合に依存するモデルに現れる。
本稿では,行列幅制約を用いたスパースMNNLSの新しい定式化を提案する。
提案した2段階の手法は,カラムワイドおよびグローバルの両方に適用された最先端のスパース符号よりも精度の高い結果が得られることを示す。
- 参考スコア（独自算出の注目度）: 22.679160149512377
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Nonnegative least squares problems with multiple right-hand sides (MNNLS)
arise in models that rely on additive linear combinations. In particular, they
are at the core of most nonnegative matrix factorization algorithms and have
many applications. The nonnegativity constraint is known to naturally favor
sparsity, that is, solutions with few non-zero entries. However, it is often
useful to further enhance this sparsity, as it improves the interpretability of
the results and helps reducing noise, which leads to the sparse MNNLS problem.
In this paper, as opposed to most previous works that enforce sparsity column-
or row-wise, we first introduce a novel formulation for sparse MNNLS, with a
matrix-wise sparsity constraint. Then, we present a two-step algorithm to
tackle this problem. The first step divides sparse MNNLS in subproblems, one
per column of the original problem. It then uses different algorithms to
produce, either exactly or approximately, a Pareto front for each subproblem,
that is, to produce a set of solutions representing different tradeoffs between
reconstruction error and sparsity. The second step selects solutions among
these Pareto fronts in order to build a sparsity-constrained matrix that
minimizes the reconstruction error. We perform experiments on facial and
hyperspectral images, and we show that our proposed two-step approach provides
more accurate results than state-of-the-art sparse coding heuristics applied
both column-wise and globally.
- Abstract（参考訳）: 多重右辺 (MNNLS) を持つ非負の最小二乗問題は、加法線形結合に依存するモデルに現れる。
特に、ほとんどの非負行列分解アルゴリズムの中核にあり、多くの応用がある。
非負性制約(nonnegativity constraint)は、自然にスパーシティ、すなわち非零成分の少ない解を好むことが知られている。
しかし、結果の解釈性が向上し、ノイズの低減に役立ち、スパースMNNLS問題につながるため、この空間性をさらに強化することがしばしば有用である。
本稿では,スパースカラムを行方向に強制するこれまでのほとんどの研究とは対照的に,まず,行列方向のスパース制約を持つスパースMNNLSの新しい定式化を導入する。
次に,この問題に取り組むための二段階アルゴリズムを提案する。
最初のステップでは、sparse mnnlをサブプロブレムで分割し、元の問題の列に1つずつ分割する。
次に、異なるアルゴリズムを用いて、各サブプロブレムのパレートフロント、すなわち、再構成エラーとスパーシティの間の異なるトレードオフを表す一連のソリューションを生成する。
第2のステップは、復元エラーを最小限に抑えるスパーシティ制約付きマトリックスを構築するために、これらのパレートフロント間の解を選択する。
顔とハイパースペクトルの画像について実験を行い,提案する2段階のアプローチは,カラム単位とグローバルの両方に適用した,最先端のスパース符号化ヒューリスティックよりも精度の高い結果を提供することを示した。
関連論文リスト
- Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳（メタデータ） (2022-11-16T18:59:54Z) - A Fast Scale-Invariant Algorithm for Non-negative Least Squares with
Non-negative Data [18.81091632124107]
我々は、データ自体が非負であることを示し、この場合の非負性は問題を容易にすることを示した。
特に、制約のない最小二乗問題のオラクルの複雑さは、データ行列定数の1つで必ずスケールするが、非負のデータを含む非負の最小二乗問題は乗法誤差に解けることを示す。
論文 参考訳（メタデータ） (2022-03-08T02:02:32Z) - Sparse Quadratic Optimisation over the Stiefel Manifold with Application
to Permutation Synchronisation [71.27989298860481]
二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。
そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-30T19:17:35Z) - Nonlinear matrix recovery using optimization on the Grassmann manifold [18.655422834567577]
本研究では,列が部分空間の結合などの非線形構造に従う部分観測された高階クラスタリング行列の復元問題について検討する。
交代極限はクルディカ・ロジャシ性質を用いて一意点に収束することを示す。
論文 参考訳（メタデータ） (2021-09-13T16:13:13Z) - Near-Optimal Algorithms for Linear Algebra in the Current Matrix
Multiplication Time [46.31710224483631]
既存の定数係数近似のスケッチ次元における対数的要素について、Nelson and Nguyen (FOCS, 2013) の主な開問題を回避する方法を示す。
私たちが使用している重要なテクニックは、不確実性原理と抽出子に基づくIndykの明示的なマッピングです。
ランク計算と列の線形独立部分集合の探索という基本的な問題に対して、我々のアルゴリズムはCheung, Kwok, Lau (JACM, 2013)を改良し、それぞれ定数係数と$log(n)$-factorの範囲内で最適である。
論文 参考訳（メタデータ） (2021-07-16T19:34:10Z) - Hashing embeddings of optimal dimension, with applications to linear
least squares [1.2891210250935143]
スケッチの射影次元$m$で最適である$sgeq 1$のスケッチ行列に対して、サブスペース埋め込み特性を提示する。
これらの結果をLinear Least Squares (LLS) の特殊なケースに適用し,これらの問題に対する汎用ソフトウェアパッケージであるSki-LLSを開発する。
論文 参考訳（メタデータ） (2021-05-25T10:35:13Z) - Solving weakly supervised regression problem using low-rank manifold
regularization [77.34726150561087]
我々は弱い教師付き回帰問題を解く。
weakly"の下では、いくつかのトレーニングポイントではラベルが知られ、未知のものもあれば、無作為なノイズの存在やリソースの欠如などの理由によって不確かであることが分かっています。
数値的な節ではモンテカルロモデルを用いて提案手法を人工と実のデータセットに適用した。
論文 参考訳（メタデータ） (2021-04-13T23:21:01Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。
まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。
次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-01-19T04:24:23Z) - Robust Low-rank Matrix Completion via an Alternating Manifold Proximal
Gradient Continuation Method [47.80060761046752]
ロバスト低ランク行列補完(RMC)は、コンピュータビジョン、信号処理、機械学習アプリケーションのために広く研究されている。
この問題は、部分的に観察された行列を低ランク行列とスパース行列の重ね合わせに分解することを目的とした。
RMCに取り組むために広く用いられるアプローチは、低ランク行列の核ノルム(低ランク性を促進するために)とスパース行列のl1ノルム(空間性を促進するために)を最小化する凸定式化を考えることである。
本稿では、近年のローワークの動機付けについて述べる。
論文 参考訳（メタデータ） (2020-08-18T04:46:22Z) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
スケッチに基づくL2正規化最小二乗問題の解法を提案する。
我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
論文 参考訳（メタデータ） (2020-06-10T15:00:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。