Back to search

University of Birmingham

Cardinality optimization problems

Abstract

dc:description.abstract

In this thesis, we discuss the cardinality minimization problem (CMP) and the cardinality constraint problem. Due to the NP-hardness of these problems, we discuss different computational and relaxation techniques for finding an approximate solution to these problems. We also discuss the l1-minimization as one of the most efficient methods for solving CMPs, and we demonstrate that the l1-minimization uses a kind of weighted l2-minimization. We show that the reweighted lj-minimization (j≥1) is very effective to locate a sparse solution to a linear system. Next, we show how to introduce different merit functions for sparsity, and how proper weights may reduce the gap between the performances of these functions for finding a sparse solution to an undetermined linear system. Furthermore, we introduce some effective computational approaches to locate a sparse solution for an underdetermined linear system. These approaches are based on reweighted lj-minimization (j≥1) algorithms. We focus on the reweighted l1-minimization, and introduce several new concave approximations to the l0-norm function. These approximations can be employed to define new weights for reweighted l1-minimization algorithms. We show how the change of parameters in reweighted algorithms may affect the performance of the algorithms for finding the solution of the cardinality minimization problem. In our experiments, the problem data were generated according to different statistical distributions, and we test the algorithms on different sparsity level of the solution of the problem. As a special case of cardinality constrained problems, we also discuss compressed sensing, restricted isometry property (RIP), and restricted isometry constant (RIC).

Degree

thesis:*
Name dc:type.qualificationname
d_ph
Level dc:type.qualificationlevel
d_ph
Grantor dc:publisher.institution
University of Birmingham
Year dc:date.issued
2013

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Abdi, Mohammad Javad

Subjects

dc:subject × 1

Rights

Language dc:language.dcterms_iso639_2
eng

Chain of custody

source
Harvested from
University of Birmingham
Base URL
etheses.bham.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Abdi, Mohammad Javad. Cardinality optimization problems. d_ph thesis, University of Birmingham, 2013.