A Faster Algorithm Solving a Generalization of Isotonic Median Regression and a Class of Fused Lasso Problems

DOI10.1137/15M1024081zbMath1383.90009MaRDI QIDQ4602345

Cheng Lu, Dorit S. Hochbaum

Publication date: 10 January 2018

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

zbMATH Keywords

minimum cutquantile regressionMarkov random fieldsisotonic median regressionfused Lassopartial order estimation

Mathematics Subject Classification ID

Linear programming (90C05) Production models (90B30)

Related Items

A unified approach for a 1D generalized total variation problem, A dynamic programming approach for generalized nearly isotonic optimization, Unnamed Item, Linear-step solvability of some folded concave and singly-parametric sparse optimization problems, Erratum: A Faster Algorithm Solving a Generalization of Isotonic Median Regression and a Class of Fused Lasso Problems, Outlier Detection in Time Series via Mixed-Integer Conic Quadratic Optimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Nonparametric function estimation subject to monotonicity, convexity and other shape constraints
• An algorithm for isotonic median regression
• Algorithms in order restricted statistical inference and the Cauchy mean value property
• Locating service centers with precedence constraints
• A data structure for dynamic trees
• A cut-based algorithm for the nonlinear dual of the minimum cost network flow problem
• Efficient computation of an isotonic median regression
• Extensions of smoothing via taut strings
• Complexity and algorithms for nonlinear optimization problems
• Multiple isotonic median regression
• Exact Algorithms for $L^1$-TV Regularization of Real-Valued or Circle-Valued Signals
• Solving the Convex Cost Integer Dual Network Flow Problem
• Learning Rule Ensembles for Ordinal Classification with Monotonicity Constraints
• Total Variation on a Tree
• An Empirical Distribution Function for Sampling with Incomplete Information
• A TEST OF HOMOGENEITY FOR ORDERED ALTERNATIVES
• THE COMPLETE AMALGAMATION INTO BLOCKS, BY WEIGHTED MEANS, OF A FINITE SET OF REAL NUMBERS
• A TEST OF HOMOGENEITY FOR ORDERED ALTERNATIVES. II
• The Pseudoflow Algorithm: A New Algorithm for the Maximum-Flow Problem
• Weighted isotonic regression under the L₁ norm
• A Fast Scaling Algorithm for Minimizing Separable Convex Functions Subject to Chain Constraints
• Establishing Consistent and Realistic Reorder Intervals in Production-Distribution Systems
• 98%-Effective Integer-Ratio Lot-Sizing for One-Warehouse Multi-Retailer Systems
• Isotonic Median Regression: A Linear Programming Approach
• Locally monotonic regression
• Lower and Upper Bounds for the Allocation Problem and Other Nonlinear Optimization Problems
• Minimizing a Convex Cost Closure Set
• Sparsity and Smoothness Via the Fused Lasso
• A Fast Parametric Maximum Flow Algorithm and Applications
• Minimizers of Cost-Functions Involving Nonsmooth Data-Fidelity Terms. Application to the Processing of Outliers
• Aspects of Total Variation RegularizedL¹Function Approximation
• Simplifications and speedups of the pseudoflow algorithm
• An efficient algorithm for image segmentation, Markov random fields and related problems
• On Estimating Monotone Parameters
• The Isotonic Regression Problem and Its Dual
• Least d-Majorized Network Flows with Inventory and Statistical Applications
• Convex separable optimization is not much harder than linear optimization