Isotonic Regression

Given a sequence A of n integers, design an algorithm to find an non-decreasing sequence B of n integers, such that \sum_{i=1}^n |A_i - B_i| is minimized.

Solution:

This problem can be solved by minimum cost flow. Here we use dynamic programming.

Let F(k, z) be the optimal objective value for the first k elements with B[k] = z. Then, we have a recurrence relation: F(k, z) = min F(k-1, x) + |zA[k]|. Thus, the problem becomes how to efficiently find the z minimizing F(k, z) for all fixed k. It can be showed that F(k, z) is a piecewise linear convex function in z and the minimizing value must be in A. Thus, the dynamic programming can be speed up by using slope optimization and find the solution in O(n lg n) time.

解法

F(k, z) 為前 k 個元素且  B[k] = 時的最佳解之值。當給定 k ,我們可得一遞回關係式:F(k, z) = min F(k-1, x) + |zA[k]|。因此問題就變成如何快速的找出最小化 F(k, z) 的 z 值。我們可以證明 F(k, z) 對於 z 是一個 piecewise linear convex 函數 ,而且可以最小化 z 值必定在 A 中。因此使用動態規劃加上斜率最佳化可以在O(n lg n)時間內找到答案。

Reference: Stackoverflow, Stackoverflow

Günter Rote, “Isotonic Regression by Dynamic Programming”

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s