HackerPapers

arXiv:1508.00952math.OC

Graphical Newton

Akshay Srinivasan, Emanuel Todorov

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

Abstract

Computing the Newton step for a generic function $f: \mathbb{R}^N \rightarrow \mathbb{R}$ takes $O(N^{3})$ flops. In this paper, we explore avenues for reducing this bound, when the computational structure of $f$ is known beforehand. It is shown that the Newton step can be computed in time, linear in the size of the computational-graph, and cubic in its tree-width.

arXiv comments
Journal reference
DOI
Subjects
math.OCOptimization and Control cs.RORobotics eess.SYSystems and Control (EESS)

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Oct 2016 to Oct 2016.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. Kalman Filter via a Simple and Intuitive Derivation [pdf] 1 comment

    • KF is essentially a symbolic unrolling of a LU decomposition. There is a graphical algorithm which makes all the minutae trivial [1]. [1] https://arxiv.org/pdf/1508.00952.pdf

      akssriView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.