On NP-Hardness of $L_1/L_2$ Minimization and Bound Theory of Nonzero Entries in Solutions Article Swipe
Min Tao
,
Xiaoping Zhang
,
Yun-Bin Zhao
·
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2409.18748
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2409.18748
The \(L_1/L_2\) norm ratio has gained significant attention as a measure of sparsity due to three merits: sharper approximation to the \(L_0\) norm compared to the \(L_1\) norm, being parameter-free and scale-invariant, and exceptional performance with highly coherent matrices. These properties have led to its successful application across a wide range of fields. While several efficient algorithms have been proposed to compute stationary points for \(L_1/L_2\) minimization problems, their computational complexity has remained open. In this paper, we prove that finding the global minimum of both constrained and unconstrained \(L_1/L_2\) models is strongly NP-hard. In addition, we establish uniform upper bounds on the \(L_2\) norm for any local minimizer of both constrained and unconstrained \(L_1/L_2\) minimization models. We also derive upper and lower bounds on the magnitudes of the nonzero entries in any local minimizer of the unconstrained model, aiding in classifying nonzero entries. Finally, we extend our analysis to demonstrate that the constrained and unconstrained \(L_p/L_q\) (\(0 < p \leq 1, 1 < q < +\infty\)) models are also strongly NP-hard.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2409.18748
- https://arxiv.org/pdf/2409.18748
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4403799354
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4403799354Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2409.18748Digital Object Identifier
- Title
-
On NP-Hardness of $L_1/L_2$ Minimization and Bound Theory of Nonzero Entries in SolutionsWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2024Year of publication
- Publication date
-
2024-09-27Full publication date if available
- Authors
-
Min Tao, Xiaoping Zhang, Yun-Bin ZhaoList of authors in order
- Landing page
-
https://arxiv.org/abs/2409.18748Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2409.18748Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2409.18748Direct OA link when available
- Concepts
-
Minification, SIGNAL (programming language), Signal recovery, Computer science, Algorithm, Computational complexity theory, Upper and lower bounds, Compressed sensing, Mathematical optimization, Mathematics, Mathematical analysis, Programming languageTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4403799354 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2409.18748 |
| ids.doi | https://doi.org/10.48550/arxiv.2409.18748 |
| ids.openalex | https://openalex.org/W4403799354 |
| fwci | |
| type | preprint |
| title | On NP-Hardness of $L_1/L_2$ Minimization and Bound Theory of Nonzero Entries in Solutions |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T10500 |
| topics[0].field.id | https://openalex.org/fields/22 |
| topics[0].field.display_name | Engineering |
| topics[0].score | 0.9988999962806702 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/2206 |
| topics[0].subfield.display_name | Computational Mechanics |
| topics[0].display_name | Sparse and Compressive Sensing Techniques |
| topics[1].id | https://openalex.org/T11447 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9804999828338623 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1711 |
| topics[1].subfield.display_name | Signal Processing |
| topics[1].display_name | Blind Source Separation Techniques |
| topics[2].id | https://openalex.org/T10688 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9643999934196472 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1707 |
| topics[2].subfield.display_name | Computer Vision and Pattern Recognition |
| topics[2].display_name | Image and Signal Denoising Methods |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C147764199 |
| concepts[0].level | 2 |
| concepts[0].score | 0.6375212669372559 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q6865248 |
| concepts[0].display_name | Minification |
| concepts[1].id | https://openalex.org/C2779843651 |
| concepts[1].level | 2 |
| concepts[1].score | 0.5507069230079651 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q7390335 |
| concepts[1].display_name | SIGNAL (programming language) |
| concepts[2].id | https://openalex.org/C2989281035 |
| concepts[2].level | 3 |
| concepts[2].score | 0.5479512214660645 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q120811 |
| concepts[2].display_name | Signal recovery |
| concepts[3].id | https://openalex.org/C41008148 |
| concepts[3].level | 0 |
| concepts[3].score | 0.5286118388175964 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[3].display_name | Computer science |
| concepts[4].id | https://openalex.org/C11413529 |
| concepts[4].level | 1 |
| concepts[4].score | 0.4909849464893341 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[4].display_name | Algorithm |
| concepts[5].id | https://openalex.org/C179799912 |
| concepts[5].level | 2 |
| concepts[5].score | 0.45703330636024475 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q205084 |
| concepts[5].display_name | Computational complexity theory |
| concepts[6].id | https://openalex.org/C77553402 |
| concepts[6].level | 2 |
| concepts[6].score | 0.4178248941898346 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q13222579 |
| concepts[6].display_name | Upper and lower bounds |
| concepts[7].id | https://openalex.org/C124851039 |
| concepts[7].level | 2 |
| concepts[7].score | 0.3737356662750244 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q2665459 |
| concepts[7].display_name | Compressed sensing |
| concepts[8].id | https://openalex.org/C126255220 |
| concepts[8].level | 1 |
| concepts[8].score | 0.3526597321033478 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q141495 |
| concepts[8].display_name | Mathematical optimization |
| concepts[9].id | https://openalex.org/C33923547 |
| concepts[9].level | 0 |
| concepts[9].score | 0.3403100371360779 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[9].display_name | Mathematics |
| concepts[10].id | https://openalex.org/C134306372 |
| concepts[10].level | 1 |
| concepts[10].score | 0.05872136354446411 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q7754 |
| concepts[10].display_name | Mathematical analysis |
| concepts[11].id | https://openalex.org/C199360897 |
| concepts[11].level | 1 |
| concepts[11].score | 0.0 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q9143 |
| concepts[11].display_name | Programming language |
| keywords[0].id | https://openalex.org/keywords/minification |
| keywords[0].score | 0.6375212669372559 |
| keywords[0].display_name | Minification |
| keywords[1].id | https://openalex.org/keywords/signal |
| keywords[1].score | 0.5507069230079651 |
| keywords[1].display_name | SIGNAL (programming language) |
| keywords[2].id | https://openalex.org/keywords/signal-recovery |
| keywords[2].score | 0.5479512214660645 |
| keywords[2].display_name | Signal recovery |
| keywords[3].id | https://openalex.org/keywords/computer-science |
| keywords[3].score | 0.5286118388175964 |
| keywords[3].display_name | Computer science |
| keywords[4].id | https://openalex.org/keywords/algorithm |
| keywords[4].score | 0.4909849464893341 |
| keywords[4].display_name | Algorithm |
| keywords[5].id | https://openalex.org/keywords/computational-complexity-theory |
| keywords[5].score | 0.45703330636024475 |
| keywords[5].display_name | Computational complexity theory |
| keywords[6].id | https://openalex.org/keywords/upper-and-lower-bounds |
| keywords[6].score | 0.4178248941898346 |
| keywords[6].display_name | Upper and lower bounds |
| keywords[7].id | https://openalex.org/keywords/compressed-sensing |
| keywords[7].score | 0.3737356662750244 |
| keywords[7].display_name | Compressed sensing |
| keywords[8].id | https://openalex.org/keywords/mathematical-optimization |
| keywords[8].score | 0.3526597321033478 |
| keywords[8].display_name | Mathematical optimization |
| keywords[9].id | https://openalex.org/keywords/mathematics |
| keywords[9].score | 0.3403100371360779 |
| keywords[9].display_name | Mathematics |
| keywords[10].id | https://openalex.org/keywords/mathematical-analysis |
| keywords[10].score | 0.05872136354446411 |
| keywords[10].display_name | Mathematical analysis |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2409.18748 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | https://arxiv.org/pdf/2409.18748 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2409.18748 |
| locations[1].id | doi:10.48550/arxiv.2409.18748 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | cc-by |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | https://openalex.org/licenses/cc-by |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.48550/arxiv.2409.18748 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5072825287 |
| authorships[0].author.orcid | https://orcid.org/0000-0003-4750-2959 |
| authorships[0].author.display_name | Min Tao |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Tao, Min |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5100363169 |
| authorships[1].author.orcid | https://orcid.org/0000-0003-0995-4989 |
| authorships[1].author.display_name | Xiaoping Zhang |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Zhang, Xiao-Ping |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5057733991 |
| authorships[2].author.orcid | https://orcid.org/0000-0002-2388-9047 |
| authorships[2].author.display_name | Yun-Bin Zhao |
| authorships[2].author_position | last |
| authorships[2].raw_author_name | Zhao, Yun-Bin |
| authorships[2].is_corresponding | False |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2409.18748 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2024-10-27T00:00:00 |
| display_name | On NP-Hardness of $L_1/L_2$ Minimization and Bound Theory of Nonzero Entries in Solutions |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T10500 |
| primary_topic.field.id | https://openalex.org/fields/22 |
| primary_topic.field.display_name | Engineering |
| primary_topic.score | 0.9988999962806702 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/2206 |
| primary_topic.subfield.display_name | Computational Mechanics |
| primary_topic.display_name | Sparse and Compressive Sensing Techniques |
| related_works | https://openalex.org/W1502442302, https://openalex.org/W1966462872, https://openalex.org/W2963726738, https://openalex.org/W2087326866, https://openalex.org/W2118132594, https://openalex.org/W2078389543, https://openalex.org/W3024569604, https://openalex.org/W4297957985, https://openalex.org/W2136676913, https://openalex.org/W2208932071 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2409.18748 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2409.18748 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/2409.18748 |
| primary_location.id | pmh:oai:arXiv.org:2409.18748 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | https://arxiv.org/pdf/2409.18748 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2409.18748 |
| publication_date | 2024-09-27 |
| publication_year | 2024 |
| referenced_works_count | 0 |
| abstract_inverted_index.1 | 162 |
| abstract_inverted_index.a | 9, 48 |
| abstract_inverted_index.p | 159 |
| abstract_inverted_index.q | 164 |
| abstract_inverted_index.1, | 161 |
| abstract_inverted_index.In | 74, 94 |
| abstract_inverted_index.We | 117 |
| abstract_inverted_index.as | 8 |
| abstract_inverted_index.in | 131, 140 |
| abstract_inverted_index.is | 91 |
| abstract_inverted_index.of | 11, 51, 84, 109, 127, 135 |
| abstract_inverted_index.on | 101, 124 |
| abstract_inverted_index.to | 14, 19, 24, 43, 60, 149 |
| abstract_inverted_index.we | 77, 96, 145 |
| abstract_inverted_index.The | 0 |
| abstract_inverted_index.and | 30, 32, 87, 112, 121, 154 |
| abstract_inverted_index.any | 106, 132 |
| abstract_inverted_index.are | 168 |
| abstract_inverted_index.due | 13 |
| abstract_inverted_index.for | 64, 105 |
| abstract_inverted_index.has | 4, 71 |
| abstract_inverted_index.its | 44 |
| abstract_inverted_index.led | 42 |
| abstract_inverted_index.our | 147 |
| abstract_inverted_index.the | 20, 25, 81, 102, 125, 128, 136, 152 |
| abstract_inverted_index.< | 158, 163, 165 |
| abstract_inverted_index.(\(0 | 157 |
| abstract_inverted_index.\leq | 160 |
| abstract_inverted_index.also | 118, 169 |
| abstract_inverted_index.been | 58 |
| abstract_inverted_index.both | 85, 110 |
| abstract_inverted_index.have | 41, 57 |
| abstract_inverted_index.norm | 2, 22, 104 |
| abstract_inverted_index.that | 79, 151 |
| abstract_inverted_index.this | 75 |
| abstract_inverted_index.wide | 49 |
| abstract_inverted_index.with | 35 |
| abstract_inverted_index.These | 39 |
| abstract_inverted_index.While | 53 |
| abstract_inverted_index.being | 28 |
| abstract_inverted_index.local | 107, 133 |
| abstract_inverted_index.lower | 122 |
| abstract_inverted_index.norm, | 27 |
| abstract_inverted_index.open. | 73 |
| abstract_inverted_index.prove | 78 |
| abstract_inverted_index.range | 50 |
| abstract_inverted_index.ratio | 3 |
| abstract_inverted_index.their | 68 |
| abstract_inverted_index.three | 15 |
| abstract_inverted_index.upper | 99, 120 |
| abstract_inverted_index.across | 47 |
| abstract_inverted_index.aiding | 139 |
| abstract_inverted_index.bounds | 100, 123 |
| abstract_inverted_index.derive | 119 |
| abstract_inverted_index.extend | 146 |
| abstract_inverted_index.gained | 5 |
| abstract_inverted_index.global | 82 |
| abstract_inverted_index.highly | 36 |
| abstract_inverted_index.model, | 138 |
| abstract_inverted_index.models | 90, 167 |
| abstract_inverted_index.paper, | 76 |
| abstract_inverted_index.points | 63 |
| abstract_inverted_index.\(L_0\) | 21 |
| abstract_inverted_index.\(L_1\) | 26 |
| abstract_inverted_index.\(L_2\) | 103 |
| abstract_inverted_index.compute | 61 |
| abstract_inverted_index.entries | 130 |
| abstract_inverted_index.fields. | 52 |
| abstract_inverted_index.finding | 80 |
| abstract_inverted_index.measure | 10 |
| abstract_inverted_index.merits: | 16 |
| abstract_inverted_index.minimum | 83 |
| abstract_inverted_index.models. | 116 |
| abstract_inverted_index.nonzero | 129, 142 |
| abstract_inverted_index.several | 54 |
| abstract_inverted_index.sharper | 17 |
| abstract_inverted_index.uniform | 98 |
| abstract_inverted_index.Finally, | 144 |
| abstract_inverted_index.NP-hard. | 93, 171 |
| abstract_inverted_index.analysis | 148 |
| abstract_inverted_index.coherent | 37 |
| abstract_inverted_index.compared | 23 |
| abstract_inverted_index.entries. | 143 |
| abstract_inverted_index.proposed | 59 |
| abstract_inverted_index.remained | 72 |
| abstract_inverted_index.sparsity | 12 |
| abstract_inverted_index.strongly | 92, 170 |
| abstract_inverted_index.addition, | 95 |
| abstract_inverted_index.attention | 7 |
| abstract_inverted_index.efficient | 55 |
| abstract_inverted_index.establish | 97 |
| abstract_inverted_index.matrices. | 38 |
| abstract_inverted_index.minimizer | 108, 134 |
| abstract_inverted_index.problems, | 67 |
| abstract_inverted_index.+\infty\)) | 166 |
| abstract_inverted_index.algorithms | 56 |
| abstract_inverted_index.complexity | 70 |
| abstract_inverted_index.magnitudes | 126 |
| abstract_inverted_index.properties | 40 |
| abstract_inverted_index.stationary | 62 |
| abstract_inverted_index.successful | 45 |
| abstract_inverted_index.\(L_1/L_2\) | 1, 65, 89, 114 |
| abstract_inverted_index.\(L_p/L_q\) | 156 |
| abstract_inverted_index.application | 46 |
| abstract_inverted_index.classifying | 141 |
| abstract_inverted_index.constrained | 86, 111, 153 |
| abstract_inverted_index.demonstrate | 150 |
| abstract_inverted_index.exceptional | 33 |
| abstract_inverted_index.performance | 34 |
| abstract_inverted_index.significant | 6 |
| abstract_inverted_index.minimization | 66, 115 |
| abstract_inverted_index.approximation | 18 |
| abstract_inverted_index.computational | 69 |
| abstract_inverted_index.unconstrained | 88, 113, 137, 155 |
| abstract_inverted_index.parameter-free | 29 |
| abstract_inverted_index.scale-invariant, | 31 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 3 |
| citation_normalized_percentile |