Title | ||
---|---|---|
Efficient Schemes for Total Variation Minimization Under Constraints in Image Processing |
Abstract | ||
---|---|---|
This paper presents new fast algorithms to minimize total variation and more generally $l^1$-norms under a general convex constraint. Such problems are standards of image processing. The algorithms are based on a recent advance in convex optimization proposed by Yurii Nesterov. Depending on the regularity of the data fidelity term, we solve either a primal problem or a dual problem. First we show that standard first-order schemes allow one to get solutions of precision $\epsilon$ in $O(\frac{1}{\epsilon^2})$ iterations at worst. We propose a scheme that allows one to obtain a solution of precision $\epsilon$ in $O(\frac{1}{\epsilon})$ iterations for a general convex constraint. For a strongly convex constraint, we solve a dual problem with a scheme that requires $O(\frac{1}{\sqrt{\epsilon}})$ iterations to get a solution of precision $\epsilon$. Finally we perform some numerical experiments which confirm the theoretical results on various problems of image processing. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1137/070696143 | SIAM J. Scientific Computing |
Keywords | Field | DocType |
dual problem,data fidelity term,primal problem,total variation minimization,convex optimization,various problem,convex constraint,image processing,efficient schemes,standard first-order scheme,general convex constraint,yurii nesterov,total variation,complexity,duality | Discrete mathematics,Fidelity,Mathematical optimization,Mathematical analysis,Image processing,Regular polygon,Convex function,Total variation minimization,Duality (optimization),Convex optimization,Mathematics | Journal |
Volume | Issue | ISSN |
31 | 3 | 1064-8275 |
Citations | PageRank | References |
76 | 4.56 | 33 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Pierre Weiss | 1 | 84 | 5.85 |
Laure Blanc-Féraud | 2 | 536 | 63.97 |
Gilles Aubert | 3 | 1275 | 108.17 |