A primal-dual active-set method for non-negativity constrained total variation deblurring problems

D. Krishnan, Ping Lin, A. M. Yip

    Research output: Contribution to journalArticle

    29 Citations (Scopus)

    Abstract

    This paper studies image deblurring problems using a total variation-based model, with a non-negativity constraint. The addition of the non-negativity constraint improves the quality of the solutions, but makes the solution process a difficult one. The contribution of our work is a fast and robust numerical algorithm to solve the non-negatively constrained problem. To overcome the nondifferentiability of the total variation norm, we formulate the constrained deblurring problem as a primal-dual program which is a variant of the formulation proposed by Chan, Golub, and Mulet for unconstrained problems. Here, dual refers to a combination of the Lagrangian and Fenchel duals. To solve the constrained primal-dual program, we use a semi-smooth Newton's method. We exploit the relationship between the semi-smooth Newton's method and the primal-dual active set method to achieve considerable simplification of the computations. The main advantages of our proposed scheme are: no parameters need significant adjustment, a standard inverse preconditioner works very well, quadratic rate of local convergence (theoretical and numerical), numerical evidence of global convergence, and high accuracy of solving the optimality system. The scheme shows robustness of performance over a wide range of parameters. A comprehensive set of numerical comparisons are provided against other methods to solve the same problem which show the speed and accuracy advantages of our scheme.
    Original languageEnglish
    Pages (from-to)2766-2777
    Number of pages12
    JournalIEEE Transactions on Image Processing
    Volume16
    Issue number11
    DOIs
    Publication statusPublished - Nov 2007

    Fingerprint

    Newton-Raphson method

    Keywords

    • Image deblurring
    • Non-negativity
    • Primal-dual active-set
    • Semismooth Newton's method
    • Total variation

    Cite this

    @article{2341c7239d0d4f2a96e8dcdc155ea74d,
    title = "A primal-dual active-set method for non-negativity constrained total variation deblurring problems",
    abstract = "This paper studies image deblurring problems using a total variation-based model, with a non-negativity constraint. The addition of the non-negativity constraint improves the quality of the solutions, but makes the solution process a difficult one. The contribution of our work is a fast and robust numerical algorithm to solve the non-negatively constrained problem. To overcome the nondifferentiability of the total variation norm, we formulate the constrained deblurring problem as a primal-dual program which is a variant of the formulation proposed by Chan, Golub, and Mulet for unconstrained problems. Here, dual refers to a combination of the Lagrangian and Fenchel duals. To solve the constrained primal-dual program, we use a semi-smooth Newton's method. We exploit the relationship between the semi-smooth Newton's method and the primal-dual active set method to achieve considerable simplification of the computations. The main advantages of our proposed scheme are: no parameters need significant adjustment, a standard inverse preconditioner works very well, quadratic rate of local convergence (theoretical and numerical), numerical evidence of global convergence, and high accuracy of solving the optimality system. The scheme shows robustness of performance over a wide range of parameters. A comprehensive set of numerical comparisons are provided against other methods to solve the same problem which show the speed and accuracy advantages of our scheme.",
    keywords = "Image deblurring, Non-negativity, Primal-dual active-set, Semismooth Newton's method, Total variation",
    author = "D. Krishnan and Ping Lin and Yip, {A. M.}",
    note = "dc.publisher: Institute of Electrical and Electronics Engineers",
    year = "2007",
    month = "11",
    doi = "10.1109/TIP.2007.908079",
    language = "English",
    volume = "16",
    pages = "2766--2777",
    journal = "IEEE Transactions on Image Processing",
    issn = "1057-7149",
    publisher = "Institute of Electrical and Electronics Engineers",
    number = "11",

    }

    A primal-dual active-set method for non-negativity constrained total variation deblurring problems. / Krishnan, D.; Lin, Ping; Yip, A. M.

    In: IEEE Transactions on Image Processing, Vol. 16, No. 11, 11.2007, p. 2766-2777.

    Research output: Contribution to journalArticle

    TY - JOUR

    T1 - A primal-dual active-set method for non-negativity constrained total variation deblurring problems

    AU - Krishnan, D.

    AU - Lin, Ping

    AU - Yip, A. M.

    N1 - dc.publisher: Institute of Electrical and Electronics Engineers

    PY - 2007/11

    Y1 - 2007/11

    N2 - This paper studies image deblurring problems using a total variation-based model, with a non-negativity constraint. The addition of the non-negativity constraint improves the quality of the solutions, but makes the solution process a difficult one. The contribution of our work is a fast and robust numerical algorithm to solve the non-negatively constrained problem. To overcome the nondifferentiability of the total variation norm, we formulate the constrained deblurring problem as a primal-dual program which is a variant of the formulation proposed by Chan, Golub, and Mulet for unconstrained problems. Here, dual refers to a combination of the Lagrangian and Fenchel duals. To solve the constrained primal-dual program, we use a semi-smooth Newton's method. We exploit the relationship between the semi-smooth Newton's method and the primal-dual active set method to achieve considerable simplification of the computations. The main advantages of our proposed scheme are: no parameters need significant adjustment, a standard inverse preconditioner works very well, quadratic rate of local convergence (theoretical and numerical), numerical evidence of global convergence, and high accuracy of solving the optimality system. The scheme shows robustness of performance over a wide range of parameters. A comprehensive set of numerical comparisons are provided against other methods to solve the same problem which show the speed and accuracy advantages of our scheme.

    AB - This paper studies image deblurring problems using a total variation-based model, with a non-negativity constraint. The addition of the non-negativity constraint improves the quality of the solutions, but makes the solution process a difficult one. The contribution of our work is a fast and robust numerical algorithm to solve the non-negatively constrained problem. To overcome the nondifferentiability of the total variation norm, we formulate the constrained deblurring problem as a primal-dual program which is a variant of the formulation proposed by Chan, Golub, and Mulet for unconstrained problems. Here, dual refers to a combination of the Lagrangian and Fenchel duals. To solve the constrained primal-dual program, we use a semi-smooth Newton's method. We exploit the relationship between the semi-smooth Newton's method and the primal-dual active set method to achieve considerable simplification of the computations. The main advantages of our proposed scheme are: no parameters need significant adjustment, a standard inverse preconditioner works very well, quadratic rate of local convergence (theoretical and numerical), numerical evidence of global convergence, and high accuracy of solving the optimality system. The scheme shows robustness of performance over a wide range of parameters. A comprehensive set of numerical comparisons are provided against other methods to solve the same problem which show the speed and accuracy advantages of our scheme.

    KW - Image deblurring

    KW - Non-negativity

    KW - Primal-dual active-set

    KW - Semismooth Newton's method

    KW - Total variation

    U2 - 10.1109/TIP.2007.908079

    DO - 10.1109/TIP.2007.908079

    M3 - Article

    VL - 16

    SP - 2766

    EP - 2777

    JO - IEEE Transactions on Image Processing

    JF - IEEE Transactions on Image Processing

    SN - 1057-7149

    IS - 11

    ER -