Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: How to find a bounding line?
Replies: 39   Last Post: Jul 12, 2013 5:39 AM

 Messages: [ Previous | Next ]
 Leon Aigret Posts: 31 Registered: 12/2/12
Re: How to find a bounding line?
Posted: Jul 11, 2013 7:50 PM

On Thu, 11 Jul 2013 15:54:29 -0700 (PDT), ols6000@sbcglobal.net wrote:

>On Thursday, July 11, 2013 2:11:21 PM UTC-7, Leon Aigret wrote:
>> The cost function SUM(y_i - y(x_i)) for the line y = a x + b becomes
>> SUM(y_i - a x_i - b) = N (y_mean - a x_mean - b), so minimizing this
>> function corresponds with maximizing a x_mean +b. Calculating x_mean
>> is O(N), but has to be done just once.

>
>Carrying this one step further, minimizing the cost function is just maximizing a. The problem with this is that the cost is subject to y_i-y(x_i)>=0

At this point in the analysis the cost function can and will be used
to evaluate every line y = a x + b which lies below all data points
(i.e. y_i-y(x_i)>=0 for all i) or, equivalently, lies below all points
of the convex hull, so just maximizing a is not an option.

>> Actually, since a x_mean + b has the geometrical interpretation of
>> y-coordinate of the intersection of y = a x + b and x = x_mean,
>> repeated evaluation of that expression can be replaced by the
>> geometrical argument that the best line is the line with the highest
>> intersection point, which must (and can) be the point where the line
>> x = x_mean reaches the convex hull.

>
>Can you explain what you mean by "the line with the highest intersection point"?

More precisely: the line that, among all lines y = a x + b that lie
below the convex hull, has the highest intersection point
(x_mean, a x_mean + b) with the line x = x_mean.

Leon

Date Subject Author
7/7/13 Woody
7/7/13 Scott Berg
7/7/13 Peter Percival
7/7/13 Woody
7/7/13 quasi
7/7/13 quasi
7/8/13 quasi
7/8/13 Woody
7/8/13 quasi
7/8/13 LudovicoVan
7/8/13 LudovicoVan
7/10/13 Woody
7/10/13 quasi
7/8/13 Leon Aigret
7/8/13 Woody
7/10/13 Leon Aigret
7/10/13 Leon Aigret
7/10/13 Woody
7/10/13 RGVickson@shaw.ca
7/10/13 Woody
7/10/13 quasi
7/7/13 quasi
7/7/13 quasi
7/7/13 quasi
7/8/13 William Elliot
7/8/13 Peter Percival
7/8/13 quasi
7/11/13 Woody
7/11/13 quasi
7/11/13 LudovicoVan
7/11/13 quasi
7/11/13 Leon Aigret
7/11/13 Woody
7/11/13 Leon Aigret
7/12/13 Woody
7/12/13 Leon Aigret
7/11/13 Woody
7/12/13 quasi
7/12/13 Woody
7/12/13 quasi