Title   name
2007년 KSIAM 봄 학술대회
 
  Title
  Speaker   Chan, Tony  
  Date 2007-05-26
  Host
  Place KAIST
  File  의 1 번째 Real Media 동영상입니다. 의 1 번째 강연자료입니다.
 
Abstract : Total variation(TV) minimizing models have become one of the most popular and successfulmethodologies for image restoration since their introduction by Rudin, Osher and Fatemi [1].The TV-based models can eliminate oscillations(noise) while preserving sharp edges. Recently,TV minimization has also been extended to other image precessing tasks as impaintings, deconvolutionsand decompositions et al. In spite of their success, computing numerical solutionsof TV models is very challenging. This is mainly due to the non-smoothness, high non-linearityand spatial stiffness of the TV regularization term R jruj.In the talk, I’ll first give a survey of some existing primal methods. In the original paper[1],Rudin et al. modified TV to smooth R qjruj2 + ¯ and solve the associated Euler-Lagrangeequation by steepest descent method. The method is very slow due to the time step constraintsfor parabolic type equations. The fixed-point method developed Vogel et al. is faster but theconvergence is still linear. Newton’s method is quadratic, but has a very small domain of convergencefor the primal TV problem and fails to converge for small ¯.In [2], Chan et al. introduced a dual variable w = ru pjruj2+¯and obtain the primal-dual system.The primal dual system fold out the singularity and nonlinearity onto high dimensions andhence is more suitable to adopt Newton’s method. The quadratic convergence for Newton’smethod is demonstrated in [2] with relatively small ¯ which makes no visual difference. Manyother algorithms have also been developed to solve the dual problem ever since. These includelocal relaxation methods and barrier penalty methods et al. A major advance in this directionwas made recently by Chambolle[3], in which he obtained an explicit analytic formula forthe Lagrange multipliers for the constraints in the dual problem. It allowed him to develop agradient descent type method that is global convergent and doesn’t need the smooth parameter¯. More recently Goldfarb and Yin[4] made an observation that TV minimization model canbe transformed into a Second-Order Cone Programming problem(SOCP) and hence can becomputed by standard SOCP solvers.Finally, I will also show the connections between recently developed duality-based methodswith our primal-dual Newton method(CGM).