{"id":{"repo_id":"birmingham","oai_identifier":"oai:etheses.bham.ac.uk:4620"},"canonical_url":"https://search.ndltd.org/etd/birmingham/oai:etheses.bham.ac.uk:4620","repository":{"repo_id":"birmingham","name":"University of Birmingham","base_url":"https://etheses.bham.ac.uk/cgi/oai2"},"display":{"title":"Cardinality optimization problems","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 l\\(_1\\)-minimization as one of the most efficient methods for solving CMPs, and we demonstrate that the l\\(_1\\)-minimization uses a kind of weighted l\\(_2\\)-minimization. We show that the reweighted l\\(_j\\)-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 l\\(_j\\)-minimization (j≥1) algorithms. We focus on the reweighted l\\(_1\\)-minimization, and introduce several new concave approximations to the l\\(_0\\)-norm function. These approximations can be employed to define new weights for reweighted l\\(_1\\)-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).","abstract_html":"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 l<span class=\"etd-inline-math\"><sub>1</sub></span>-minimization as one of the most efficient methods for solving CMPs, and we demonstrate that the l<span class=\"etd-inline-math\"><sub>1</sub></span>-minimization uses a kind of weighted l<span class=\"etd-inline-math\"><sub>2</sub></span>-minimization. We show that the reweighted l<span class=\"etd-inline-math\"><sub>j</sub></span>-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 l<span class=\"etd-inline-math\"><sub>j</sub></span>-minimization (j≥1) algorithms. We focus on the reweighted l<span class=\"etd-inline-math\"><sub>1</sub></span>-minimization, and introduce several new concave approximations to the l<span class=\"etd-inline-math\"><sub>0</sub></span>-norm function. These approximations can be employed to define new weights for reweighted l<span class=\"etd-inline-math\"><sub>1</sub></span>-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).","abstract_has_math":true,"creators":["Abdi, Mohammad Javad"],"institution":"University of Birmingham","degree_name":"d_ph","degree_level":"d_ph","degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2013,"date_issued":"2013-12","date_published":"2013-12","updated_at":"2026-11-19T09:27:45Z","subjects":["QA Mathematics"],"languages":["eng"],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":null,"outbound_label":null,"outbound_source":null,"record_url":null,"record_label":null,"record_kind":null,"record_source":null,"download_url":"http://etheses.bham.ac.uk//id/eprint/4620/1/Abdi13PhD.pdf","download_label":"Download PDF","download_source":"dc:identifier.uri","access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://etheses.bham.ac.uk/cgi/oai2?verb=GetRecord&metadataPrefix=uketd_dc&identifier=oai%3Aetheses.bham.ac.uk%3A4620","prefix":"uketd_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.sponsor","label":"Sponsor","values":["na"]},{"key":"dc:creator","label":"Author","values":["Abdi, Mohammad Javad"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2013-12"]},{"key":"dc:date.issued","label":"Date","values":["2013-12"]},{"key":"dc:publisher.department","label":"Dc Publisher Department","values":["College of Engineering & Physical Sciences","School of Mathematics"]},{"key":"dc:publisher.institution","label":"Dc Publisher Institution","values":["University of Birmingham"]},{"key":"dc:relation.isreferencedby","label":"Dc Relation Isreferencedby","values":["http://etheses.bham.ac.uk//id/eprint/4620/"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"dc:type.qualificationlevel","label":"Dc Type Qualificationlevel","values":["d_ph"]},{"key":"dc:type.qualificationname","label":"Dc Type Qualificationname","values":["d_ph"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["QA Mathematics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.dcterms_iso639_2","label":"Language (ISO 639-2)","values":["eng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://etheses.bham.ac.uk//id/eprint/4620/1/Abdi13PhD.pdf","http://etheses.bham.ac.uk//id/eprint/4620/2/Decl_IS_Abdi13PhD.pdf"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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 l\\(_1\\)-minimization as one of the most efficient methods for solving CMPs, and we demonstrate that the l\\(_1\\)-minimization uses a kind of weighted l\\(_2\\)-minimization. We show that the reweighted l\\(_j\\)-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 l\\(_j\\)-minimization (j≥1) algorithms. We focus on the reweighted l\\(_1\\)-minimization, and introduce several new concave approximations to the l\\(_0\\)-norm function. These approximations can be employed to define new weights for reweighted l\\(_1\\)-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)."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dcterms:accessrights","label":"Dcterms Accessrights","values":["public","staffonly"]},{"key":"dc:title","label":"Title","values":["Cardinality optimization problems"]}]}],"canonical_facts":{"dc:contributor.sponsor":["na"],"dc:creator":["Abdi, Mohammad Javad"],"dc:date":["2013-12"],"dc:date.issued":["2013-12"],"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 l\\(_1\\)-minimization as one of the most efficient methods for solving CMPs, and we demonstrate that the l\\(_1\\)-minimization uses a kind of weighted l\\(_2\\)-minimization. We show that the reweighted l\\(_j\\)-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 l\\(_j\\)-minimization (j≥1) algorithms. We focus on the reweighted l\\(_1\\)-minimization, and introduce several new concave approximations to the l\\(_0\\)-norm function. These approximations can be employed to define new weights for reweighted l\\(_1\\)-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)."],"dc:format":["application/pdf"],"dc:identifier.uri":["http://etheses.bham.ac.uk//id/eprint/4620/1/Abdi13PhD.pdf","http://etheses.bham.ac.uk//id/eprint/4620/2/Decl_IS_Abdi13PhD.pdf"],"dc:language.dcterms_iso639_2":["eng"],"dc:publisher.department":["College of Engineering & Physical Sciences","School of Mathematics"],"dc:publisher.institution":["University of Birmingham"],"dc:relation.isreferencedby":["http://etheses.bham.ac.uk//id/eprint/4620/"],"dc:subject":["QA Mathematics"],"dcterms:accessrights":["public","staffonly"],"dc:title":["Cardinality optimization problems"],"dc:type":["Thesis"],"dc:type.qualificationlevel":["d_ph"],"dc:type.qualificationname":["d_ph"]},"updated_at":"2026-11-19T09:27:45Z"}