Many (most?) column subset selection criteria are NP hard Article Swipe
We consider a variety of criteria for selecting k representative columns from a real matrix A with rank(A)>=k. The criteria include the following optimization problems: absolute volume and S-optimality maximization; norm and condition minimization in the two-norm, Frobenius norm and Schatten p-norms for p>2; stable rank maximization; and the new criterion of relative volume maximization. We show that these criteria are NP hard and do not admit polynomial time approximation schemes (PTAS). To formulate the optimization problems as decision problems, we derive optimal values for the subset selection criteria, as well as expressions for partitioned pseudo-inverses.
Related Topics
Concepts
Mathematics
Minification
Matrix norm
Norm (philosophy)
Selection (genetic algorithm)
Variety (cybernetics)
Mathematical optimization
Rank (graph theory)
Optimization problem
Matrix (chemical analysis)
Time complexity
Combinatorics
Polynomial
Approximation algorithm
Subset sum problem
Computational complexity theory
Volume (thermodynamics)
Algorithm
Feature selection
Low-rank approximation
Decision problem
Discrete mathematics
Column (typography)
Linear programming
Metadata
- Type
- article
- Landing Page
- http://arxiv.org/abs/2511.02740
- https://arxiv.org/pdf/2511.02740
- OA Status
- green
- OpenAlex ID
- https://openalex.org/W7104182886
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W7104182886Canonical identifier for this work in OpenAlex
- Title
-
Many (most?) column subset selection criteria are NP hardWork title
- Type
-
articleOpenAlex work type
- Publication year
-
2025Year of publication
- Publication date
-
2025-11-04Full publication date if available
- Authors
-
Ipsen, Ilse C. F., Saibaba, Arvind K.List of authors in order
- Landing page
-
https://arxiv.org/abs/2511.02740Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2511.02740Direct 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/2511.02740Direct OA link when available
- Concepts
-
Mathematics, Minification, Matrix norm, Norm (philosophy), Selection (genetic algorithm), Variety (cybernetics), Mathematical optimization, Rank (graph theory), Optimization problem, Matrix (chemical analysis), Time complexity, Combinatorics, Polynomial, Approximation algorithm, Subset sum problem, Computational complexity theory, Volume (thermodynamics), Algorithm, Feature selection, Low-rank approximation, Decision problem, Discrete mathematics, Column (typography), Linear programmingTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
Full payload
| id | https://openalex.org/W7104182886 |
|---|---|
| doi | |
| ids.openalex | https://openalex.org/W7104182886 |
| fwci | 0.0 |
| type | article |
| title | Many (most?) column subset selection criteria are NP hard |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T10963 |
| topics[0].field.id | https://openalex.org/fields/26 |
| topics[0].field.display_name | Mathematics |
| topics[0].score | 0.4420434534549713 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/2612 |
| topics[0].subfield.display_name | Numerical Analysis |
| topics[0].display_name | Advanced Optimization Algorithms Research |
| topics[1].id | https://openalex.org/T11612 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.16018228232860565 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1702 |
| topics[1].subfield.display_name | Artificial Intelligence |
| topics[1].display_name | Stochastic Gradient Optimization Techniques |
| topics[2].id | https://openalex.org/T10720 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.0390956848859787 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1703 |
| topics[2].subfield.display_name | Computational Theory and Mathematics |
| topics[2].display_name | Complexity and Algorithms in Graphs |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C33923547 |
| concepts[0].level | 0 |
| concepts[0].score | 0.7588973045349121 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[0].display_name | Mathematics |
| concepts[1].id | https://openalex.org/C147764199 |
| concepts[1].level | 2 |
| concepts[1].score | 0.5483342409133911 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q6865248 |
| concepts[1].display_name | Minification |
| concepts[2].id | https://openalex.org/C92207270 |
| concepts[2].level | 3 |
| concepts[2].score | 0.543668806552887 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q939253 |
| concepts[2].display_name | Matrix norm |
| concepts[3].id | https://openalex.org/C191795146 |
| concepts[3].level | 2 |
| concepts[3].score | 0.5022154450416565 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q3878446 |
| concepts[3].display_name | Norm (philosophy) |
| concepts[4].id | https://openalex.org/C81917197 |
| concepts[4].level | 2 |
| concepts[4].score | 0.48726046085357666 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q628760 |
| concepts[4].display_name | Selection (genetic algorithm) |
| concepts[5].id | https://openalex.org/C136197465 |
| concepts[5].level | 2 |
| concepts[5].score | 0.48415037989616394 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q1729295 |
| concepts[5].display_name | Variety (cybernetics) |
| concepts[6].id | https://openalex.org/C126255220 |
| concepts[6].level | 1 |
| concepts[6].score | 0.4682583510875702 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q141495 |
| concepts[6].display_name | Mathematical optimization |
| concepts[7].id | https://openalex.org/C164226766 |
| concepts[7].level | 2 |
| concepts[7].score | 0.4500442147254944 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q7293202 |
| concepts[7].display_name | Rank (graph theory) |
| concepts[8].id | https://openalex.org/C137836250 |
| concepts[8].level | 2 |
| concepts[8].score | 0.4465455412864685 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q984063 |
| concepts[8].display_name | Optimization problem |
| concepts[9].id | https://openalex.org/C106487976 |
| concepts[9].level | 2 |
| concepts[9].score | 0.4293094873428345 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q685816 |
| concepts[9].display_name | Matrix (chemical analysis) |
| concepts[10].id | https://openalex.org/C311688 |
| concepts[10].level | 2 |
| concepts[10].score | 0.41493120789527893 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q2393193 |
| concepts[10].display_name | Time complexity |
| concepts[11].id | https://openalex.org/C114614502 |
| concepts[11].level | 1 |
| concepts[11].score | 0.3836657702922821 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[11].display_name | Combinatorics |
| concepts[12].id | https://openalex.org/C90119067 |
| concepts[12].level | 2 |
| concepts[12].score | 0.35949379205703735 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q43260 |
| concepts[12].display_name | Polynomial |
| concepts[13].id | https://openalex.org/C148764684 |
| concepts[13].level | 2 |
| concepts[13].score | 0.3548724949359894 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q621751 |
| concepts[13].display_name | Approximation algorithm |
| concepts[14].id | https://openalex.org/C109275537 |
| concepts[14].level | 3 |
| concepts[14].score | 0.3146638870239258 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q1154420 |
| concepts[14].display_name | Subset sum problem |
| concepts[15].id | https://openalex.org/C179799912 |
| concepts[15].level | 2 |
| concepts[15].score | 0.30850282311439514 |
| concepts[15].wikidata | https://www.wikidata.org/wiki/Q205084 |
| concepts[15].display_name | Computational complexity theory |
| concepts[16].id | https://openalex.org/C20556612 |
| concepts[16].level | 2 |
| concepts[16].score | 0.30646079778671265 |
| concepts[16].wikidata | https://www.wikidata.org/wiki/Q4469374 |
| concepts[16].display_name | Volume (thermodynamics) |
| concepts[17].id | https://openalex.org/C11413529 |
| concepts[17].level | 1 |
| concepts[17].score | 0.296016126871109 |
| concepts[17].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[17].display_name | Algorithm |
| concepts[18].id | https://openalex.org/C148483581 |
| concepts[18].level | 2 |
| concepts[18].score | 0.28879687190055847 |
| concepts[18].wikidata | https://www.wikidata.org/wiki/Q446488 |
| concepts[18].display_name | Feature selection |
| concepts[19].id | https://openalex.org/C90199385 |
| concepts[19].level | 3 |
| concepts[19].score | 0.2849672734737396 |
| concepts[19].wikidata | https://www.wikidata.org/wiki/Q6692777 |
| concepts[19].display_name | Low-rank approximation |
| concepts[20].id | https://openalex.org/C115988155 |
| concepts[20].level | 2 |
| concepts[20].score | 0.28189772367477417 |
| concepts[20].wikidata | https://www.wikidata.org/wiki/Q3262192 |
| concepts[20].display_name | Decision problem |
| concepts[21].id | https://openalex.org/C118615104 |
| concepts[21].level | 1 |
| concepts[21].score | 0.27451735734939575 |
| concepts[21].wikidata | https://www.wikidata.org/wiki/Q121416 |
| concepts[21].display_name | Discrete mathematics |
| concepts[22].id | https://openalex.org/C2780551164 |
| concepts[22].level | 3 |
| concepts[22].score | 0.2679153084754944 |
| concepts[22].wikidata | https://www.wikidata.org/wiki/Q2306599 |
| concepts[22].display_name | Column (typography) |
| concepts[23].id | https://openalex.org/C41045048 |
| concepts[23].level | 2 |
| concepts[23].score | 0.2541802227497101 |
| concepts[23].wikidata | https://www.wikidata.org/wiki/Q202843 |
| concepts[23].display_name | Linear programming |
| keywords[0].id | https://openalex.org/keywords/minification |
| keywords[0].score | 0.5483342409133911 |
| keywords[0].display_name | Minification |
| keywords[1].id | https://openalex.org/keywords/matrix-norm |
| keywords[1].score | 0.543668806552887 |
| keywords[1].display_name | Matrix norm |
| keywords[2].id | https://openalex.org/keywords/norm |
| keywords[2].score | 0.5022154450416565 |
| keywords[2].display_name | Norm (philosophy) |
| keywords[3].id | https://openalex.org/keywords/selection |
| keywords[3].score | 0.48726046085357666 |
| keywords[3].display_name | Selection (genetic algorithm) |
| keywords[4].id | https://openalex.org/keywords/variety |
| keywords[4].score | 0.48415037989616394 |
| keywords[4].display_name | Variety (cybernetics) |
| keywords[5].id | https://openalex.org/keywords/rank |
| keywords[5].score | 0.4500442147254944 |
| keywords[5].display_name | Rank (graph theory) |
| keywords[6].id | https://openalex.org/keywords/optimization-problem |
| keywords[6].score | 0.4465455412864685 |
| keywords[6].display_name | Optimization problem |
| keywords[7].id | https://openalex.org/keywords/matrix |
| keywords[7].score | 0.4293094873428345 |
| keywords[7].display_name | Matrix (chemical analysis) |
| language | |
| locations[0].id | pmh:oai:arXiv.org:2511.02740 |
| 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 | cc-by |
| locations[0].pdf_url | https://arxiv.org/pdf/2511.02740 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| locations[0].license_id | https://openalex.org/licenses/cc-by |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2511.02740 |
| indexed_in | arxiv |
| authorships[0].author.id | https://openalex.org/A4222650828 |
| authorships[0].author.orcid | |
| authorships[0].author.display_name | Ipsen, Ilse C. F. |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Ipsen, Ilse C. F. |
| authorships[0].is_corresponding | True |
| authorships[1].author.id | https://openalex.org/A4226181903 |
| authorships[1].author.orcid | |
| authorships[1].author.display_name | Saibaba, Arvind K. |
| authorships[1].author_position | last |
| authorships[1].raw_author_name | Saibaba, Arvind K. |
| authorships[1].is_corresponding | False |
| has_content.pdf | True |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2511.02740 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-11-06T00:00:00 |
| display_name | Many (most?) column subset selection criteria are NP hard |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-07T23:23:33.682996 |
| primary_topic.id | https://openalex.org/T10963 |
| primary_topic.field.id | https://openalex.org/fields/26 |
| primary_topic.field.display_name | Mathematics |
| primary_topic.score | 0.4420434534549713 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/2612 |
| primary_topic.subfield.display_name | Numerical Analysis |
| primary_topic.display_name | Advanced Optimization Algorithms Research |
| cited_by_count | 0 |
| locations_count | 1 |
| best_oa_location.id | pmh:oai:arXiv.org:2511.02740 |
| 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 | cc-by |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2511.02740 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| best_oa_location.license_id | https://openalex.org/licenses/cc-by |
| 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/2511.02740 |
| primary_location.id | pmh:oai:arXiv.org:2511.02740 |
| 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 | cc-by |
| primary_location.pdf_url | https://arxiv.org/pdf/2511.02740 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| primary_location.license_id | https://openalex.org/licenses/cc-by |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2511.02740 |
| publication_date | 2025-11-04 |
| publication_year | 2025 |
| referenced_works_count | 0 |
| abstract_inverted_index.A | 15 |
| abstract_inverted_index.a | 2, 12 |
| abstract_inverted_index.k | 8 |
| abstract_inverted_index.NP | 61 |
| abstract_inverted_index.To | 72 |
| abstract_inverted_index.We | 0, 55 |
| abstract_inverted_index.as | 77, 89, 91 |
| abstract_inverted_index.do | 64 |
| abstract_inverted_index.in | 34 |
| abstract_inverted_index.of | 4, 51 |
| abstract_inverted_index.we | 80 |
| abstract_inverted_index.The | 18 |
| abstract_inverted_index.and | 27, 31, 39, 47, 63 |
| abstract_inverted_index.are | 60 |
| abstract_inverted_index.for | 6, 42, 84, 93 |
| abstract_inverted_index.new | 49 |
| abstract_inverted_index.not | 65 |
| abstract_inverted_index.the | 21, 35, 48, 74, 85 |
| abstract_inverted_index.from | 11 |
| abstract_inverted_index.hard | 62 |
| abstract_inverted_index.norm | 30, 38 |
| abstract_inverted_index.p>2; | 43 |
| abstract_inverted_index.rank | 45 |
| abstract_inverted_index.real | 13 |
| abstract_inverted_index.show | 56 |
| abstract_inverted_index.that | 57 |
| abstract_inverted_index.time | 68 |
| abstract_inverted_index.well | 90 |
| abstract_inverted_index.with | 16 |
| abstract_inverted_index.admit | 66 |
| abstract_inverted_index.these | 58 |
| abstract_inverted_index.derive | 81 |
| abstract_inverted_index.matrix | 14 |
| abstract_inverted_index.stable | 44 |
| abstract_inverted_index.subset | 86 |
| abstract_inverted_index.values | 83 |
| abstract_inverted_index.volume | 26, 53 |
| abstract_inverted_index.(PTAS). | 71 |
| abstract_inverted_index.columns | 10 |
| abstract_inverted_index.include | 20 |
| abstract_inverted_index.optimal | 82 |
| abstract_inverted_index.p-norms | 41 |
| abstract_inverted_index.schemes | 70 |
| abstract_inverted_index.variety | 3 |
| abstract_inverted_index.Schatten | 40 |
| abstract_inverted_index.absolute | 25 |
| abstract_inverted_index.consider | 1 |
| abstract_inverted_index.criteria | 5, 19, 59 |
| abstract_inverted_index.decision | 78 |
| abstract_inverted_index.problems | 76 |
| abstract_inverted_index.relative | 52 |
| abstract_inverted_index.Frobenius | 37 |
| abstract_inverted_index.condition | 32 |
| abstract_inverted_index.criteria, | 88 |
| abstract_inverted_index.criterion | 50 |
| abstract_inverted_index.following | 22 |
| abstract_inverted_index.formulate | 73 |
| abstract_inverted_index.problems, | 79 |
| abstract_inverted_index.problems: | 24 |
| abstract_inverted_index.selecting | 7 |
| abstract_inverted_index.selection | 87 |
| abstract_inverted_index.two-norm, | 36 |
| abstract_inverted_index.polynomial | 67 |
| abstract_inverted_index.expressions | 92 |
| abstract_inverted_index.partitioned | 94 |
| abstract_inverted_index.rank(A)>=k. | 17 |
| abstract_inverted_index.S-optimality | 28 |
| abstract_inverted_index.minimization | 33 |
| abstract_inverted_index.optimization | 23, 75 |
| abstract_inverted_index.approximation | 69 |
| abstract_inverted_index.maximization. | 54 |
| abstract_inverted_index.maximization; | 29, 46 |
| abstract_inverted_index.representative | 9 |
| abstract_inverted_index.pseudo-inverses. | 95 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 2 |
| citation_normalized_percentile.value | 0.83261694 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | True |