Durfee, David, Gao, Yu, Rao, Anup B and Wild, Sebastian 
ORCID: 0000-0002-6061-9177
(2019)
Efficient Second-Order Shape-Constrained Function Fitting.
.
|
Text
1905.02149v2.pdf - Submitted version Download (720kB) | Preview |
Abstract
We give an algorithm to compute a one-dimensional shape-constrained function that best fits given data in weighted-L∞$$L_{\infty }$$ norm. We give a single algorithm that works for a variety of commonly studied shape constraints including monotonicity, Lipschitz-continuity and convexity, and more generally, any shape constraint expressible by bounds on first- and/or second-order differences. Our algorithm computes an approximation with additive error ϵ$$\epsilon $$ in OnlogUϵ$$O\left( n \log \frac{U}{\epsilon } \right) $$ time, where U captures the range of input values. We also give a simple greedy algorithm that runs in O(n) time for the special case of unweighted L∞$$L_{\infty }$$ convex regression. These are the first (near-)linear-time algorithms for second-order-constrained function fitting. To achieve these results, we use a novel geometric interpretation of the underlying dynamic programming problem. We further show that a generalization of the corresponding problems to directed acyclic graphs (DAGs) is as difficult as linear programming.
| Item Type: | Conference Item (Unspecified) |
|---|---|
| Additional Information: | accepted for WADS 2019; (v2 fixes various typos) |
| Uncontrolled Keywords: | 46 Information and Computing Sciences |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 15 Aug 2019 14:38 |
| Last Modified: | 13 May 2025 17:20 |
| DOI: | 10.1007/978-3-030-24766-9_29 |
| Related Websites: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3051854 |
Available Versions of this Item
- Efficient Second-Order Shape-Constrained Function Fitting. (deposited 15 Aug 2019 14:38) [Currently Displayed]
Altmetric
Altmetric