Sparse Approximate Solutions to Max-Plus Equations

被引：1
作者：
Tsilivis, Nikos [1 ]
Tsiamis, Anastasios [2 ]
Maragos, Petros [1 ]
机构：
[1] Natl Tech Univ Athens, Sch ECE, Athens, Greece
[2] Univ Penn, ESE Dept, SEAS, Philadelphia, PA 19104 USA
来源：
DISCRETE GEOMETRY AND MATHEMATICAL MORPHOLOGY, DGMM 2021 | 2021年 / 12708卷
关键词：
Sparsity; Max-plus algebra; Submodular optimization; ALGEBRA;
D O I：
10.1007/978-3-030-76657-3_39
中图分类号：
学科分类号：
摘要：
In this work, we study the problem of finding approximate, with minimum support set, solutions to matrix max-plus equations, which we call sparse approximate solutions. We show how one can obtain such solutions efficiently and in polynomial time for any l(p) approximation error. Subsequently, we propose a method for pruning morphological neural networks, based on the developed theory.
引用
收藏
页码：538 / 550
页数：13
相关论文
共 25 条
  • [1] TROPICAL POLYHEDRA ARE EQUIVALENT TO MEAN PAYOFF GAMES
    Akian, Marianne
    Gaubert, Stephane
    Guterman, Alexander
    [J]. INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 2012, 22 (01)
  • [2] Baccelli F., 1992, Synchronization and Linearity: An Algebra for Discrete Event Systems
  • [3] Learning with Submodular Functions: A Convex Optimization Perspective
    Bach, Francis
    [J]. FOUNDATIONS AND TRENDS IN MACHINE LEARNING, 2013, 6 (2-3): : 145 - 373
  • [4] Butkovic P, 2010, SPRINGER MONOGR MATH, P1, DOI 10.1007/978-1-84996-299-5
  • [5] Stable signal recovery from incomplete and inaccurate measurements
    Candes, Emmanuel J.
    Romberg, Justin K.
    Tao, Terence
    [J]. COMMUNICATIONS ON PURE AND APPLIED MATHEMATICS, 2006, 59 (08) : 1207 - 1223
  • [6] Morphological Perceptrons: Geometry and Training Algorithms
    Charisopoulos, Vasileios
    Maragos, Petros
    [J]. MATHEMATICAL MORPHOLOGY AND ITS APPLICATIONS TO SIGNAL AND IMAGE PROCESSING (ISMM 2017), 2017, 10225 : 3 - 15
  • [7] Cuninghame-Green R., 1979, Minimax Algebra, V1st, P258, DOI [10.1007/978-3-642-48708-8, DOI 10.1007/978-3-642-48708-8]
  • [8] Das A, 2018, J MACH LEARN RES, V19
  • [9] Compressed sensing
    Donoho, DL
    [J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 2006, 52 (04) : 1289 - 1306
  • [10] Elad M, 2010, SPARSE AND REDUNDANT REPRESENTATIONS, P3, DOI 10.1007/978-1-4419-7011-4_1
123