Linear Programming: Data Fitting

Linear Programming: Data Fitting Steve Gu Mar 21, 2008 Outline Data fitting (Ref: pp 250) Data fitting using LP Data fitting X Y 1 2 2

5 3 8 Y X Data fitting How to fit the model y cx to the following data set using Chebyshev criterion? X Y 1

2 2 5 3 8 Chebyshevs criterion: minimize the largest absolute deviation: ri yi y ( xi ) Chebyshev Criterion max i yi y ( xi ) Goal : minimize A min max problem!

More Formal Statement X 1 2 3 Y 2 5 8 subject to: r max i yi cxi Goal : min r r (2 c) 0 r (2 c) 0 r (5 2c) 0 r (5 2c) 0 r (8 3c) 0 r (8 3c) 0 Interpret Geometrically r (2 c) 0 r (2 c) 0

r (5 2c) 0 r (5 2c) 0 r (8 3c) 0 r (8 3c) 0 r 8 6 Feasible region 4 2 1 2

3 4 5 c Interpret Geometrically r r (8 3c) 0 r (2 c) 0 c 2.5, r 0.5 Therefore, 2.5 is the

optimal value of c and the residual error is 0.5 8 6 Feasible region 4 2 Optimal solution 1 2 3

4 5 c More general problem Given N points (X1,Y1),(X2,Y2),,(XN,YN), How to fit the model y=cx using Chebyshev criterion? max i yi y ( xi ) Goal : minimize Data fitting using Linear Programming Whats the Goal? min r, where r= max i yi cxi What are the Unknowns?

r and c What are the constraints? Compare to 3-points case: r (2 c) 0 r (2 c) 0 r (5 2c) 0 r (5 2c) 0 r (8 3c) 0 r (8 3c) 0 Data fitting using Linear Programming r ( y1 cx1 ) 0 r x1c y1

r ( y1 cx1 ) 0 r x1c y1 r ( y2 cx2 ) 0 r x2 c y2 r ( y2 cx2 ) 0 r x2 c y2 ... r ( yN 1 cxN 1 ) 0 ... r xN 1c y N 1

r ( y N 1 cxN 1 ) 0 r xN 1c y N 1 r ( yN cxN ) 0 r xN c y N r ( y N cxN ) 0 r xN c y N Data fitting using Linear Programming r cx1 y1 r cx1 y1 r cx2 y2

r cx2 y2 ... r cxN 1 y N 1 1 x1 y1 1 x1 y1 r

c 1 xN yN 1 xN yN r cxN 1 y N 1 r cxN yN r cxN yN Ax b

Data fitting using Linear Programming 1 x1 y1 1 x y 1 1

r A , b , x c 1 xN yN 1 xN yN

Define : 1 f 0 constraints: Ax b objective: T max f x LP in MATLAB Use command: linprog Do type help linprog !

Example: X=linprog(f,A,b) solves the linear programming problem: min f'*x subject to: A*x <= b LP in MATLAB Results: Fitting data using LP Results: Fitting data using LP c=1.0039 r=18.1304 End: Q&A Thanks

Recently Viewed Presentations

  • Mood and Tone in Literature - WordPress.com

    Mood and Tone in Literature - WordPress.com

    Mood and Tone. TONE ... The door swings open to reveal all of my family members standing around the Christmas tree. The lights are twinkling and the fireplace is roaring with a warm fire. Everyone is singing Christmas carols as...
  • XXX, A Network Initiative

    XXX, A Network Initiative

    King Range Partners Make It Happen. A Network Initiative. Rachel Sowards Thompson. Interpretive Specialist. King Range National Conservation Area. U.S.D.I. Bureau of Land Management
  • PowerPoint Presentation

    PowerPoint Presentation

    AIS-AIMSG/12 Briefing to ANC 23 October 2015 * AIS-AIM Study Group Active since end 2008 Objectives Global strategy/roadmap for the transition from AIS to AIM SARPs/Guidance for a standard AICM/AIXM to enable global digital data exchange Other material required to...
  • Accumulating Linguistic and Socio-Economic Capital on the Margin

    Accumulating Linguistic and Socio-Economic Capital on the Margin

    Standard language ideology: the two sides. is "a bias toward an abstract, idealized homogenous language, which is imposed and maintained by dominant institutionsand which has as its model the written language, but which is drawn primarily from the spoken language...
  • PowerPoint Presentation

    PowerPoint Presentation

    John Young, Commander of the Apollo 16 mission . John Young, Commander of the Apollo 16 mission saluting the flag. The Lunar Module is behind Young, with the Lunar Roving Vehicle parked next to it. This picture shows several interesting...
  • The X-Ray Telescope for Solar-B Results of the

    The X-Ray Telescope for Solar-B Results of the

    The X-Ray Telescope for Solar-B Results of the Calibration Tests and Predicted Performance Edward DeLuca for the XRT Team Contributors MSFC XRCF Jeff McCracken Cary Reily Jay Carpenter Jeff Kegley Rich Siler Dave Watson Ernie Wright Galen Zirstein Joey Norwood...
  • The Early Greeks - PC&#92;|MAC

    The Early Greeks - PC\|MAC

    Define acropolis and agora. Name the requirements for citizenship in the Greek city-states. Sparta and Athens Chapter 4, Section 2, page 124 Chapter 4, Section 2 Objectives After this lesson, students will be able to: describe how tyrants seized control...
  • Period 2 1607-1754 - Braly U.S. History

    Period 2 1607-1754 - Braly U.S. History

    The "Old Lights" (established religious leaders) lost some of their influence in the church. People began to realize that they didn't need the higher authority in order to learn from the Bible "New Lights" broke away and formed new denominations...