The Complexity of Computing (Almost) Unitary Matrices With $\eps$-Copies of the Fourier Transform Article Swipe
Nir Ailon
,
Gal Yehuda
·
YOU?
·
· 2016
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.1604.02557
YOU?
·
· 2016
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.1604.02557
The complexity of computing the Fourier transform is a longstanding open problem. Very recently, Ailon (2013, 2014, 2015) showed in a collection of papers that, roughly speaking, a speedup of the Fourier transform computation implies numerical ill-condition. The papers also quantify this tradeoff. The main method for proving these results is via a potential function called quasi-entropy, reminiscent of Shannon entropy. The quasi-entropy method opens new doors to understanding the computational complexity of the important Fourier transformation. However, it suffers from various obvious limitations. This paper, motivated by one such limitation, partly overcomes it, while at the same time sheds llight on new interesting, and problems on the intersection of computational complexity and group theory. The paper also explains why this research direction, if fruitful, has a chance of solving much bigger questions about the complexity of the Fourier transform.
Related Topics
Concepts
Unitary state
Fourier transform
Discrete Fourier transform (general)
Unitary matrix
Fast Fourier transform
Computer science
Mathematics
Algebra over a field
Algorithm
Pure mathematics
Fourier analysis
Fractional Fourier transform
Mathematical analysis
Political science
Law
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/1604.02557
- https://arxiv.org/pdf/1604.02557
- OA Status
- green
- References
- 28
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W2920916362
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W2920916362Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.1604.02557Digital Object Identifier
- Title
-
The Complexity of Computing (Almost) Unitary Matrices With $\eps$-Copies of the Fourier TransformWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2016Year of publication
- Publication date
-
2016-04-09Full publication date if available
- Authors
-
Nir Ailon, Gal YehudaList of authors in order
- Landing page
-
https://arxiv.org/abs/1604.02557Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/1604.02557Direct 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/1604.02557Direct OA link when available
- Concepts
-
Unitary state, Fourier transform, Discrete Fourier transform (general), Unitary matrix, Fast Fourier transform, Computer science, Mathematics, Algebra over a field, Algorithm, Pure mathematics, Fourier analysis, Fractional Fourier transform, Mathematical analysis, Political science, LawTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- References (count)
-
28Number of works referenced by this work
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W2920916362 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.1604.02557 |
| ids.doi | https://doi.org/10.48550/arxiv.1604.02557 |
| ids.mag | 2920916362 |
| ids.openalex | https://openalex.org/W2920916362 |
| fwci | |
| type | preprint |
| title | The Complexity of Computing (Almost) Unitary Matrices With $\eps$-Copies of the Fourier Transform |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T10792 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9991000294685364 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1703 |
| topics[0].subfield.display_name | Computational Theory and Mathematics |
| topics[0].display_name | Matrix Theory and Algorithms |
| topics[1].id | https://openalex.org/T11210 |
| topics[1].field.id | https://openalex.org/fields/26 |
| topics[1].field.display_name | Mathematics |
| topics[1].score | 0.9980000257492065 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/2604 |
| topics[1].subfield.display_name | Applied Mathematics |
| topics[1].display_name | Mathematical Analysis and Transform Methods |
| topics[2].id | https://openalex.org/T11716 |
| topics[2].field.id | https://openalex.org/fields/26 |
| topics[2].field.display_name | Mathematics |
| topics[2].score | 0.9979000091552734 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/2613 |
| topics[2].subfield.display_name | Statistics and Probability |
| topics[2].display_name | Random Matrices and Applications |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C67820243 |
| concepts[0].level | 2 |
| concepts[0].score | 0.809424638748169 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q179164 |
| concepts[0].display_name | Unitary state |
| concepts[1].id | https://openalex.org/C102519508 |
| concepts[1].level | 2 |
| concepts[1].score | 0.6252367496490479 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q6520159 |
| concepts[1].display_name | Fourier transform |
| concepts[2].id | https://openalex.org/C57733114 |
| concepts[2].level | 5 |
| concepts[2].score | 0.5458120107650757 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q1006032 |
| concepts[2].display_name | Discrete Fourier transform (general) |
| concepts[3].id | https://openalex.org/C96214315 |
| concepts[3].level | 3 |
| concepts[3].score | 0.4665776193141937 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q727103 |
| concepts[3].display_name | Unitary matrix |
| concepts[4].id | https://openalex.org/C75172450 |
| concepts[4].level | 2 |
| concepts[4].score | 0.4408150315284729 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q623950 |
| concepts[4].display_name | Fast Fourier transform |
| concepts[5].id | https://openalex.org/C41008148 |
| concepts[5].level | 0 |
| concepts[5].score | 0.3681636452674866 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[5].display_name | Computer science |
| concepts[6].id | https://openalex.org/C33923547 |
| concepts[6].level | 0 |
| concepts[6].score | 0.36595356464385986 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[6].display_name | Mathematics |
| concepts[7].id | https://openalex.org/C136119220 |
| concepts[7].level | 2 |
| concepts[7].score | 0.34756070375442505 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q1000660 |
| concepts[7].display_name | Algebra over a field |
| concepts[8].id | https://openalex.org/C11413529 |
| concepts[8].level | 1 |
| concepts[8].score | 0.310950368642807 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[8].display_name | Algorithm |
| concepts[9].id | https://openalex.org/C202444582 |
| concepts[9].level | 1 |
| concepts[9].score | 0.2861369252204895 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q837863 |
| concepts[9].display_name | Pure mathematics |
| concepts[10].id | https://openalex.org/C203024314 |
| concepts[10].level | 3 |
| concepts[10].score | 0.26814305782318115 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q1365258 |
| concepts[10].display_name | Fourier analysis |
| concepts[11].id | https://openalex.org/C76563020 |
| concepts[11].level | 4 |
| concepts[11].score | 0.26204732060432434 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q4817582 |
| concepts[11].display_name | Fractional Fourier transform |
| concepts[12].id | https://openalex.org/C134306372 |
| concepts[12].level | 1 |
| concepts[12].score | 0.17243963479995728 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q7754 |
| concepts[12].display_name | Mathematical analysis |
| concepts[13].id | https://openalex.org/C17744445 |
| concepts[13].level | 0 |
| concepts[13].score | 0.10175076127052307 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q36442 |
| concepts[13].display_name | Political science |
| concepts[14].id | https://openalex.org/C199539241 |
| concepts[14].level | 1 |
| concepts[14].score | 0.0 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q7748 |
| concepts[14].display_name | Law |
| keywords[0].id | https://openalex.org/keywords/unitary-state |
| keywords[0].score | 0.809424638748169 |
| keywords[0].display_name | Unitary state |
| keywords[1].id | https://openalex.org/keywords/fourier-transform |
| keywords[1].score | 0.6252367496490479 |
| keywords[1].display_name | Fourier transform |
| keywords[2].id | https://openalex.org/keywords/discrete-fourier-transform |
| keywords[2].score | 0.5458120107650757 |
| keywords[2].display_name | Discrete Fourier transform (general) |
| keywords[3].id | https://openalex.org/keywords/unitary-matrix |
| keywords[3].score | 0.4665776193141937 |
| keywords[3].display_name | Unitary matrix |
| keywords[4].id | https://openalex.org/keywords/fast-fourier-transform |
| keywords[4].score | 0.4408150315284729 |
| keywords[4].display_name | Fast Fourier transform |
| keywords[5].id | https://openalex.org/keywords/computer-science |
| keywords[5].score | 0.3681636452674866 |
| keywords[5].display_name | Computer science |
| keywords[6].id | https://openalex.org/keywords/mathematics |
| keywords[6].score | 0.36595356464385986 |
| keywords[6].display_name | Mathematics |
| keywords[7].id | https://openalex.org/keywords/algebra-over-a-field |
| keywords[7].score | 0.34756070375442505 |
| keywords[7].display_name | Algebra over a field |
| keywords[8].id | https://openalex.org/keywords/algorithm |
| keywords[8].score | 0.310950368642807 |
| keywords[8].display_name | Algorithm |
| keywords[9].id | https://openalex.org/keywords/pure-mathematics |
| keywords[9].score | 0.2861369252204895 |
| keywords[9].display_name | Pure mathematics |
| keywords[10].id | https://openalex.org/keywords/fourier-analysis |
| keywords[10].score | 0.26814305782318115 |
| keywords[10].display_name | Fourier analysis |
| keywords[11].id | https://openalex.org/keywords/fractional-fourier-transform |
| keywords[11].score | 0.26204732060432434 |
| keywords[11].display_name | Fractional Fourier transform |
| keywords[12].id | https://openalex.org/keywords/mathematical-analysis |
| keywords[12].score | 0.17243963479995728 |
| keywords[12].display_name | Mathematical analysis |
| keywords[13].id | https://openalex.org/keywords/political-science |
| keywords[13].score | 0.10175076127052307 |
| keywords[13].display_name | Political science |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:1604.02557 |
| 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/1604.02557 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | |
| 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/1604.02557 |
| locations[1].id | doi:10.48550/arxiv.1604.02557 |
| 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 | |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | |
| 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.1604.02557 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5033770678 |
| authorships[0].author.orcid | |
| authorships[0].author.display_name | Nir Ailon |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Nir Ailon |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5082992148 |
| authorships[1].author.orcid | |
| authorships[1].author.display_name | Gal Yehuda |
| authorships[1].author_position | last |
| authorships[1].raw_author_name | Gal Yehuda |
| authorships[1].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/1604.02557 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | The Complexity of Computing (Almost) Unitary Matrices With $\eps$-Copies of the Fourier Transform |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T10792 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9991000294685364 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1703 |
| primary_topic.subfield.display_name | Computational Theory and Mathematics |
| primary_topic.display_name | Matrix Theory and Algorithms |
| related_works | https://openalex.org/W2154006536, https://openalex.org/W2348800014, https://openalex.org/W2365391860, https://openalex.org/W1999313313, https://openalex.org/W1820187807, https://openalex.org/W2155491755, https://openalex.org/W4362564158, https://openalex.org/W2499716529, https://openalex.org/W2085939569, https://openalex.org/W2963658971 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:1604.02557 |
| 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/1604.02557 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | |
| 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/1604.02557 |
| primary_location.id | pmh:oai:arXiv.org:1604.02557 |
| 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/1604.02557 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | |
| 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/1604.02557 |
| publication_date | 2016-04-09 |
| publication_year | 2016 |
| referenced_works | https://openalex.org/W2027377011, https://openalex.org/W2115755118, https://openalex.org/W2798909945, https://openalex.org/W822096598, https://openalex.org/W2008776938, https://openalex.org/W2949848962, https://openalex.org/W2963527076, https://openalex.org/W1507039213, https://openalex.org/W2059985428, https://openalex.org/W1985814307, https://openalex.org/W2045390367, https://openalex.org/W1482204718, https://openalex.org/W1850985299, https://openalex.org/W1965075539, https://openalex.org/W2171810522, https://openalex.org/W2061171222, https://openalex.org/W2009813398, https://openalex.org/W2127901211, https://openalex.org/W2257409780, https://openalex.org/W116230093, https://openalex.org/W1779006005, https://openalex.org/W1972710063, https://openalex.org/W1899006432, https://openalex.org/W2170835539, https://openalex.org/W2885803187, https://openalex.org/W2084466783, https://openalex.org/W1919432017, https://openalex.org/W2520311215 |
| referenced_works_count | 28 |
| abstract_inverted_index.a | 8, 20, 27, 52, 126 |
| abstract_inverted_index.at | 95 |
| abstract_inverted_index.by | 87 |
| abstract_inverted_index.if | 123 |
| abstract_inverted_index.in | 19 |
| abstract_inverted_index.is | 7, 50 |
| abstract_inverted_index.it | 78 |
| abstract_inverted_index.of | 2, 22, 29, 58, 72, 109, 128, 136 |
| abstract_inverted_index.on | 101, 106 |
| abstract_inverted_index.to | 67 |
| abstract_inverted_index.The | 0, 37, 43, 61, 115 |
| abstract_inverted_index.and | 104, 112 |
| abstract_inverted_index.for | 46 |
| abstract_inverted_index.has | 125 |
| abstract_inverted_index.it, | 93 |
| abstract_inverted_index.new | 65, 102 |
| abstract_inverted_index.one | 88 |
| abstract_inverted_index.the | 4, 30, 69, 73, 96, 107, 134, 137 |
| abstract_inverted_index.via | 51 |
| abstract_inverted_index.why | 119 |
| abstract_inverted_index.This | 84 |
| abstract_inverted_index.Very | 12 |
| abstract_inverted_index.also | 39, 117 |
| abstract_inverted_index.from | 80 |
| abstract_inverted_index.main | 44 |
| abstract_inverted_index.much | 130 |
| abstract_inverted_index.open | 10 |
| abstract_inverted_index.same | 97 |
| abstract_inverted_index.such | 89 |
| abstract_inverted_index.this | 41, 120 |
| abstract_inverted_index.time | 98 |
| abstract_inverted_index.2014, | 16 |
| abstract_inverted_index.2015) | 17 |
| abstract_inverted_index.Ailon | 14 |
| abstract_inverted_index.about | 133 |
| abstract_inverted_index.doors | 66 |
| abstract_inverted_index.group | 113 |
| abstract_inverted_index.opens | 64 |
| abstract_inverted_index.paper | 116 |
| abstract_inverted_index.sheds | 99 |
| abstract_inverted_index.that, | 24 |
| abstract_inverted_index.these | 48 |
| abstract_inverted_index.while | 94 |
| abstract_inverted_index.(2013, | 15 |
| abstract_inverted_index.bigger | 131 |
| abstract_inverted_index.called | 55 |
| abstract_inverted_index.chance | 127 |
| abstract_inverted_index.llight | 100 |
| abstract_inverted_index.method | 45, 63 |
| abstract_inverted_index.paper, | 85 |
| abstract_inverted_index.papers | 23, 38 |
| abstract_inverted_index.partly | 91 |
| abstract_inverted_index.showed | 18 |
| abstract_inverted_index.Fourier | 5, 31, 75, 138 |
| abstract_inverted_index.Shannon | 59 |
| abstract_inverted_index.implies | 34 |
| abstract_inverted_index.obvious | 82 |
| abstract_inverted_index.proving | 47 |
| abstract_inverted_index.results | 49 |
| abstract_inverted_index.roughly | 25 |
| abstract_inverted_index.solving | 129 |
| abstract_inverted_index.speedup | 28 |
| abstract_inverted_index.suffers | 79 |
| abstract_inverted_index.theory. | 114 |
| abstract_inverted_index.various | 81 |
| abstract_inverted_index.However, | 77 |
| abstract_inverted_index.entropy. | 60 |
| abstract_inverted_index.explains | 118 |
| abstract_inverted_index.function | 54 |
| abstract_inverted_index.problem. | 11 |
| abstract_inverted_index.problems | 105 |
| abstract_inverted_index.quantify | 40 |
| abstract_inverted_index.research | 121 |
| abstract_inverted_index.computing | 3 |
| abstract_inverted_index.fruitful, | 124 |
| abstract_inverted_index.important | 74 |
| abstract_inverted_index.motivated | 86 |
| abstract_inverted_index.numerical | 35 |
| abstract_inverted_index.overcomes | 92 |
| abstract_inverted_index.potential | 53 |
| abstract_inverted_index.questions | 132 |
| abstract_inverted_index.recently, | 13 |
| abstract_inverted_index.speaking, | 26 |
| abstract_inverted_index.tradeoff. | 42 |
| abstract_inverted_index.transform | 6, 32 |
| abstract_inverted_index.collection | 21 |
| abstract_inverted_index.complexity | 1, 71, 111, 135 |
| abstract_inverted_index.direction, | 122 |
| abstract_inverted_index.transform. | 139 |
| abstract_inverted_index.computation | 33 |
| abstract_inverted_index.limitation, | 90 |
| abstract_inverted_index.reminiscent | 57 |
| abstract_inverted_index.interesting, | 103 |
| abstract_inverted_index.intersection | 108 |
| abstract_inverted_index.limitations. | 83 |
| abstract_inverted_index.longstanding | 9 |
| abstract_inverted_index.computational | 70, 110 |
| abstract_inverted_index.quasi-entropy | 62 |
| abstract_inverted_index.understanding | 68 |
| abstract_inverted_index.ill-condition. | 36 |
| abstract_inverted_index.quasi-entropy, | 56 |
| abstract_inverted_index.transformation. | 76 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 2 |
| citation_normalized_percentile |