IFSM fractal image compression with entropy and sparsity constraints

A sequential quadratic programming approach

Herb Kunze, Davide La Torre, Jianyi Lin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

We consider the inverse problem associated with IFSM: Given a target function f, find an IFSM, such that its fixed point f is sufficiently close to f in the Lp distance. Forte and Vrscay [1] showed how to reduce this problem to a quadratic optimization model. In this paper, we extend the collage-based method developed by Kunze, La Torre and Vrscay ([2][3][4]), by proposing the minimization of the 1-norm instead of the 0-norm. In fact, optimization problems involving the 0-norm are combinatorial in nature, and hence in general NP-hard. To overcome these difficulties, we introduce the 1-norm and propose a Sequential Quadratic Programming algorithm to solve the corresponding inverse problem. As in Kunze, La Torre and Vrscay [3] in our formulation, the minimization of collage error is treated as a multi-criteria problem that includes three different and conflicting criteria i.e., collage error, entropy and sparsity. This multi-criteria program is solved by means of a scalarization technique which reduces the model to a single-criterion program by combining all objective functions with different trade-off weights. The results of some numerical computations are presented.

Original languageEnglish
Title of host publicationICNPAA 2016 World Congress
Subtitle of host publication11th International Conference on Mathematical Problems in Engineering, Aerospace and Sciences
PublisherAmerican Institute of Physics Inc.
Volume1798
ISBN (Electronic)9780735414648
DOIs
Publication statusPublished - Jan 27 2017
Event11th International Conference on Mathematical Problems in Engineering, Aerospace and Sciences, ICNPAA 2016 - La Rochelle, France
Duration: Jul 4 2016Jul 8 2016

Conference

Conference11th International Conference on Mathematical Problems in Engineering, Aerospace and Sciences, ICNPAA 2016
CountryFrance
CityLa Rochelle
Period7/4/167/8/16

Fingerprint

quadratic programming
norms
fractals
entropy
optimization
formulations

ASJC Scopus subject areas

  • Physics and Astronomy(all)

Cite this

Kunze, H., La Torre, D., & Lin, J. (2017). IFSM fractal image compression with entropy and sparsity constraints: A sequential quadratic programming approach. In ICNPAA 2016 World Congress: 11th International Conference on Mathematical Problems in Engineering, Aerospace and Sciences (Vol. 1798). [020090] American Institute of Physics Inc.. https://doi.org/10.1063/1.4972682

IFSM fractal image compression with entropy and sparsity constraints : A sequential quadratic programming approach. / Kunze, Herb; La Torre, Davide; Lin, Jianyi.

ICNPAA 2016 World Congress: 11th International Conference on Mathematical Problems in Engineering, Aerospace and Sciences. Vol. 1798 American Institute of Physics Inc., 2017. 020090.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Kunze, H, La Torre, D & Lin, J 2017, IFSM fractal image compression with entropy and sparsity constraints: A sequential quadratic programming approach. in ICNPAA 2016 World Congress: 11th International Conference on Mathematical Problems in Engineering, Aerospace and Sciences. vol. 1798, 020090, American Institute of Physics Inc., 11th International Conference on Mathematical Problems in Engineering, Aerospace and Sciences, ICNPAA 2016, La Rochelle, France, 7/4/16. https://doi.org/10.1063/1.4972682
Kunze H, La Torre D, Lin J. IFSM fractal image compression with entropy and sparsity constraints: A sequential quadratic programming approach. In ICNPAA 2016 World Congress: 11th International Conference on Mathematical Problems in Engineering, Aerospace and Sciences. Vol. 1798. American Institute of Physics Inc. 2017. 020090 https://doi.org/10.1063/1.4972682
Kunze, Herb ; La Torre, Davide ; Lin, Jianyi. / IFSM fractal image compression with entropy and sparsity constraints : A sequential quadratic programming approach. ICNPAA 2016 World Congress: 11th International Conference on Mathematical Problems in Engineering, Aerospace and Sciences. Vol. 1798 American Institute of Physics Inc., 2017.
@inproceedings{fe70cf3a59a74d3492a91ae3be5621bc,
title = "IFSM fractal image compression with entropy and sparsity constraints: A sequential quadratic programming approach",
abstract = "We consider the inverse problem associated with IFSM: Given a target function f, find an IFSM, such that its fixed point f is sufficiently close to f in the Lp distance. Forte and Vrscay [1] showed how to reduce this problem to a quadratic optimization model. In this paper, we extend the collage-based method developed by Kunze, La Torre and Vrscay ([2][3][4]), by proposing the minimization of the 1-norm instead of the 0-norm. In fact, optimization problems involving the 0-norm are combinatorial in nature, and hence in general NP-hard. To overcome these difficulties, we introduce the 1-norm and propose a Sequential Quadratic Programming algorithm to solve the corresponding inverse problem. As in Kunze, La Torre and Vrscay [3] in our formulation, the minimization of collage error is treated as a multi-criteria problem that includes three different and conflicting criteria i.e., collage error, entropy and sparsity. This multi-criteria program is solved by means of a scalarization technique which reduces the model to a single-criterion program by combining all objective functions with different trade-off weights. The results of some numerical computations are presented.",
author = "Herb Kunze and {La Torre}, Davide and Jianyi Lin",
year = "2017",
month = "1",
day = "27",
doi = "10.1063/1.4972682",
language = "English",
volume = "1798",
booktitle = "ICNPAA 2016 World Congress",
publisher = "American Institute of Physics Inc.",

}

TY - GEN

T1 - IFSM fractal image compression with entropy and sparsity constraints

T2 - A sequential quadratic programming approach

AU - Kunze, Herb

AU - La Torre, Davide

AU - Lin, Jianyi

PY - 2017/1/27

Y1 - 2017/1/27

N2 - We consider the inverse problem associated with IFSM: Given a target function f, find an IFSM, such that its fixed point f is sufficiently close to f in the Lp distance. Forte and Vrscay [1] showed how to reduce this problem to a quadratic optimization model. In this paper, we extend the collage-based method developed by Kunze, La Torre and Vrscay ([2][3][4]), by proposing the minimization of the 1-norm instead of the 0-norm. In fact, optimization problems involving the 0-norm are combinatorial in nature, and hence in general NP-hard. To overcome these difficulties, we introduce the 1-norm and propose a Sequential Quadratic Programming algorithm to solve the corresponding inverse problem. As in Kunze, La Torre and Vrscay [3] in our formulation, the minimization of collage error is treated as a multi-criteria problem that includes three different and conflicting criteria i.e., collage error, entropy and sparsity. This multi-criteria program is solved by means of a scalarization technique which reduces the model to a single-criterion program by combining all objective functions with different trade-off weights. The results of some numerical computations are presented.

AB - We consider the inverse problem associated with IFSM: Given a target function f, find an IFSM, such that its fixed point f is sufficiently close to f in the Lp distance. Forte and Vrscay [1] showed how to reduce this problem to a quadratic optimization model. In this paper, we extend the collage-based method developed by Kunze, La Torre and Vrscay ([2][3][4]), by proposing the minimization of the 1-norm instead of the 0-norm. In fact, optimization problems involving the 0-norm are combinatorial in nature, and hence in general NP-hard. To overcome these difficulties, we introduce the 1-norm and propose a Sequential Quadratic Programming algorithm to solve the corresponding inverse problem. As in Kunze, La Torre and Vrscay [3] in our formulation, the minimization of collage error is treated as a multi-criteria problem that includes three different and conflicting criteria i.e., collage error, entropy and sparsity. This multi-criteria program is solved by means of a scalarization technique which reduces the model to a single-criterion program by combining all objective functions with different trade-off weights. The results of some numerical computations are presented.

UR - http://www.scopus.com/inward/record.url?scp=85013627084&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85013627084&partnerID=8YFLogxK

U2 - 10.1063/1.4972682

DO - 10.1063/1.4972682

M3 - Conference contribution

VL - 1798

BT - ICNPAA 2016 World Congress

PB - American Institute of Physics Inc.

ER -