Structured Approximation of Toeplitz Matrices and Subspaces Article Swipe
This paper studies two structured approximation problems: (1) Recovering a corrupted low-rank Toeplitz matrix and (2) recovering the range of a Fourier matrix from a single observation. Both problems are computationally challenging because the structural constraints are difficult to enforce directly. We show that both tasks can be solved efficiently and optimally by applying the Gradient-MUSIC algorithm for spectral estimation. For a rank $r$ Toeplitz matrix ${\boldsymbol T}\in {\mathbb C}^{n\times n}$ that satisfies a regularity assumption and is corrupted by an arbitrary ${\boldsymbol E}\in {\mathbb C}^{n\times n}$ such that $\|{\boldsymbol E}\|_2\leq αn$, our algorithm outputs a Toeplitz matrix $\widehat{\boldsymbol T}$ of rank exactly $r$ such that $\|{\boldsymbol T}-\widehat{\boldsymbol T}\|_2 \leq C \sqrt r \, \|{\boldsymbol E}\|_2$, where $C,α>0$ are absolute constants. This performance guarantee is minimax optimal in $n$ and $\|{\boldsymbol E}\|_2$. We derive optimal results for the second problem as well. Our analysis provides quantitative connections between these two problems and spectral estimation. Our results are equally applicable to Hankel matrices with superficial modifications.
Related Topics
Concepts
Toeplitz matrix
Mathematics
Rank (graph theory)
Matrix (chemical analysis)
Low-rank approximation
Linear subspace
Minimax
Levinson recursion
Range (aeronautics)
Hankel matrix
Algorithm
Applied mathematics
Symmetric matrix
Mathematical optimization
Combinatorics
Discrete mathematics
Diagonalizable matrix
Matrix decomposition
Algebra over a field
Matrix analysis
Spectral properties
Minor (academic)
Metadata
- Type
- article
- Landing Page
- http://arxiv.org/abs/2511.17239
- https://arxiv.org/pdf/2511.17239
- OA Status
- green
- OpenAlex ID
- https://openalex.org/W7106597704
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W7106597704Canonical identifier for this work in OpenAlex
- Title
-
Structured Approximation of Toeplitz Matrices and SubspacesWork title
- Type
-
articleOpenAlex work type
- Publication year
-
2025Year of publication
- Publication date
-
2025-11-21Full publication date if available
- Authors
-
Fannjiang, Albert, Li WeilinList of authors in order
- Landing page
-
https://arxiv.org/abs/2511.17239Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2511.17239Direct 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.17239Direct OA link when available
- Concepts
-
Toeplitz matrix, Mathematics, Rank (graph theory), Matrix (chemical analysis), Low-rank approximation, Linear subspace, Minimax, Levinson recursion, Range (aeronautics), Hankel matrix, Algorithm, Applied mathematics, Symmetric matrix, Mathematical optimization, Combinatorics, Discrete mathematics, Diagonalizable matrix, Matrix decomposition, Algebra over a field, Matrix analysis, Spectral properties, Minor (academic)Top concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
Full payload
| id | https://openalex.org/W7106597704 |
|---|---|
| doi | |
| ids.openalex | https://openalex.org/W7106597704 |
| fwci | 0.0 |
| type | article |
| title | Structured Approximation of Toeplitz Matrices and Subspaces |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C147710293 |
| concepts[0].level | 2 |
| concepts[0].score | 0.9245063662528992 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q849428 |
| concepts[0].display_name | Toeplitz matrix |
| concepts[1].id | https://openalex.org/C33923547 |
| concepts[1].level | 0 |
| concepts[1].score | 0.7381851673126221 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[1].display_name | Mathematics |
| concepts[2].id | https://openalex.org/C164226766 |
| concepts[2].level | 2 |
| concepts[2].score | 0.58981853723526 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q7293202 |
| concepts[2].display_name | Rank (graph theory) |
| concepts[3].id | https://openalex.org/C106487976 |
| concepts[3].level | 2 |
| concepts[3].score | 0.5702216625213623 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q685816 |
| concepts[3].display_name | Matrix (chemical analysis) |
| concepts[4].id | https://openalex.org/C90199385 |
| concepts[4].level | 3 |
| concepts[4].score | 0.5552996397018433 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q6692777 |
| concepts[4].display_name | Low-rank approximation |
| concepts[5].id | https://openalex.org/C12362212 |
| concepts[5].level | 2 |
| concepts[5].score | 0.549475908279419 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q728435 |
| concepts[5].display_name | Linear subspace |
| concepts[6].id | https://openalex.org/C149728462 |
| concepts[6].level | 2 |
| concepts[6].score | 0.4794275760650635 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q751319 |
| concepts[6].display_name | Minimax |
| concepts[7].id | https://openalex.org/C122212055 |
| concepts[7].level | 3 |
| concepts[7].score | 0.4790455102920532 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q11679774 |
| concepts[7].display_name | Levinson recursion |
| concepts[8].id | https://openalex.org/C204323151 |
| concepts[8].level | 2 |
| concepts[8].score | 0.45605745911598206 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q905424 |
| concepts[8].display_name | Range (aeronautics) |
| concepts[9].id | https://openalex.org/C25023664 |
| concepts[9].level | 2 |
| concepts[9].score | 0.44843220710754395 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q1575637 |
| concepts[9].display_name | Hankel matrix |
| concepts[10].id | https://openalex.org/C11413529 |
| concepts[10].level | 1 |
| concepts[10].score | 0.42000722885131836 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[10].display_name | Algorithm |
| concepts[11].id | https://openalex.org/C28826006 |
| concepts[11].level | 1 |
| concepts[11].score | 0.3880091607570648 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q33521 |
| concepts[11].display_name | Applied mathematics |
| concepts[12].id | https://openalex.org/C54848796 |
| concepts[12].level | 3 |
| concepts[12].score | 0.3295696973800659 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q339011 |
| concepts[12].display_name | Symmetric matrix |
| concepts[13].id | https://openalex.org/C126255220 |
| concepts[13].level | 1 |
| concepts[13].score | 0.32558485865592957 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q141495 |
| concepts[13].display_name | Mathematical optimization |
| concepts[14].id | https://openalex.org/C114614502 |
| concepts[14].level | 1 |
| concepts[14].score | 0.3223639726638794 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[14].display_name | Combinatorics |
| concepts[15].id | https://openalex.org/C118615104 |
| concepts[15].level | 1 |
| concepts[15].score | 0.3133690059185028 |
| concepts[15].wikidata | https://www.wikidata.org/wiki/Q121416 |
| concepts[15].display_name | Discrete mathematics |
| concepts[16].id | https://openalex.org/C30072841 |
| concepts[16].level | 4 |
| concepts[16].score | 0.30914318561553955 |
| concepts[16].wikidata | https://www.wikidata.org/wiki/Q1767080 |
| concepts[16].display_name | Diagonalizable matrix |
| concepts[17].id | https://openalex.org/C42355184 |
| concepts[17].level | 3 |
| concepts[17].score | 0.3019059896469116 |
| concepts[17].wikidata | https://www.wikidata.org/wiki/Q1361088 |
| concepts[17].display_name | Matrix decomposition |
| concepts[18].id | https://openalex.org/C136119220 |
| concepts[18].level | 2 |
| concepts[18].score | 0.2915242910385132 |
| concepts[18].wikidata | https://www.wikidata.org/wiki/Q1000660 |
| concepts[18].display_name | Algebra over a field |
| concepts[19].id | https://openalex.org/C149488123 |
| concepts[19].level | 3 |
| concepts[19].score | 0.288326621055603 |
| concepts[19].wikidata | https://www.wikidata.org/wiki/Q17098730 |
| concepts[19].display_name | Matrix analysis |
| concepts[20].id | https://openalex.org/C2985906921 |
| concepts[20].level | 2 |
| concepts[20].score | 0.28196144104003906 |
| concepts[20].wikidata | https://www.wikidata.org/wiki/Q190524 |
| concepts[20].display_name | Spectral properties |
| concepts[21].id | https://openalex.org/C2779760435 |
| concepts[21].level | 2 |
| concepts[21].score | 0.2645569443702698 |
| concepts[21].wikidata | https://www.wikidata.org/wiki/Q5396169 |
| concepts[21].display_name | Minor (academic) |
| keywords[0].id | https://openalex.org/keywords/toeplitz-matrix |
| keywords[0].score | 0.9245063662528992 |
| keywords[0].display_name | Toeplitz matrix |
| keywords[1].id | https://openalex.org/keywords/rank |
| keywords[1].score | 0.58981853723526 |
| keywords[1].display_name | Rank (graph theory) |
| keywords[2].id | https://openalex.org/keywords/matrix |
| keywords[2].score | 0.5702216625213623 |
| keywords[2].display_name | Matrix (chemical analysis) |
| keywords[3].id | https://openalex.org/keywords/low-rank-approximation |
| keywords[3].score | 0.5552996397018433 |
| keywords[3].display_name | Low-rank approximation |
| keywords[4].id | https://openalex.org/keywords/linear-subspace |
| keywords[4].score | 0.549475908279419 |
| keywords[4].display_name | Linear subspace |
| keywords[5].id | https://openalex.org/keywords/minimax |
| keywords[5].score | 0.4794275760650635 |
| keywords[5].display_name | Minimax |
| keywords[6].id | https://openalex.org/keywords/levinson-recursion |
| keywords[6].score | 0.4790455102920532 |
| keywords[6].display_name | Levinson recursion |
| keywords[7].id | https://openalex.org/keywords/range |
| keywords[7].score | 0.45605745911598206 |
| keywords[7].display_name | Range (aeronautics) |
| language | |
| locations[0].id | pmh:oai:arXiv.org:2511.17239 |
| 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/2511.17239 |
| 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/2511.17239 |
| indexed_in | arxiv |
| authorships[0].author.id | https://openalex.org/A4228000377 |
| authorships[0].author.orcid | |
| authorships[0].author.display_name | Fannjiang, Albert |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Fannjiang, Albert |
| authorships[0].is_corresponding | True |
| authorships[1].author.id | https://openalex.org/A2441886824 |
| authorships[1].author.orcid | |
| authorships[1].author.display_name | Li Weilin |
| authorships[1].author_position | last |
| authorships[1].raw_author_name | Li, Weilin |
| 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/2511.17239 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-11-25T00:00:00 |
| display_name | Structured Approximation of Toeplitz Matrices and Subspaces |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-25T14:47:58.456640 |
| primary_topic | |
| cited_by_count | 0 |
| locations_count | 1 |
| best_oa_location.id | pmh:oai:arXiv.org:2511.17239 |
| 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/2511.17239 |
| 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/2511.17239 |
| primary_location.id | pmh:oai:arXiv.org:2511.17239 |
| 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/2511.17239 |
| 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/2511.17239 |
| publication_date | 2025-11-21 |
| publication_year | 2025 |
| referenced_works_count | 0 |
| abstract_inverted_index.C | 110 |
| abstract_inverted_index.a | 9, 20, 24, 61, 73, 95 |
| abstract_inverted_index.r | 112 |
| abstract_inverted_index.We | 41, 132 |
| abstract_inverted_index.\, | 113 |
| abstract_inverted_index.an | 80 |
| abstract_inverted_index.as | 140 |
| abstract_inverted_index.be | 47 |
| abstract_inverted_index.by | 52, 79 |
| abstract_inverted_index.in | 127 |
| abstract_inverted_index.is | 77, 124 |
| abstract_inverted_index.of | 19, 100 |
| abstract_inverted_index.to | 38, 159 |
| abstract_inverted_index.$n$ | 128 |
| abstract_inverted_index.$r$ | 63, 103 |
| abstract_inverted_index.(1) | 7 |
| abstract_inverted_index.(2) | 15 |
| abstract_inverted_index.For | 60 |
| abstract_inverted_index.Our | 142, 154 |
| abstract_inverted_index.T}$ | 99 |
| abstract_inverted_index.and | 14, 50, 76, 129, 151 |
| abstract_inverted_index.are | 29, 36, 118, 156 |
| abstract_inverted_index.can | 46 |
| abstract_inverted_index.for | 57, 136 |
| abstract_inverted_index.n}$ | 70, 86 |
| abstract_inverted_index.our | 92 |
| abstract_inverted_index.the | 17, 33, 54, 137 |
| abstract_inverted_index.two | 3, 149 |
| abstract_inverted_index.Both | 27 |
| abstract_inverted_index.This | 0, 121 |
| abstract_inverted_index.\leq | 109 |
| abstract_inverted_index.both | 44 |
| abstract_inverted_index.from | 23 |
| abstract_inverted_index.rank | 62, 101 |
| abstract_inverted_index.show | 42 |
| abstract_inverted_index.such | 87, 104 |
| abstract_inverted_index.that | 43, 71, 88, 105 |
| abstract_inverted_index.with | 162 |
| abstract_inverted_index.E}\in | 83 |
| abstract_inverted_index.T}\in | 67 |
| abstract_inverted_index.\sqrt | 111 |
| abstract_inverted_index.paper | 1 |
| abstract_inverted_index.range | 18 |
| abstract_inverted_index.tasks | 45 |
| abstract_inverted_index.these | 148 |
| abstract_inverted_index.well. | 141 |
| abstract_inverted_index.where | 116 |
| abstract_inverted_index.αn$, | 91 |
| abstract_inverted_index.Hankel | 160 |
| abstract_inverted_index.T}\|_2 | 108 |
| abstract_inverted_index.derive | 133 |
| abstract_inverted_index.matrix | 13, 22, 65, 97 |
| abstract_inverted_index.second | 138 |
| abstract_inverted_index.single | 25 |
| abstract_inverted_index.solved | 48 |
| abstract_inverted_index.Fourier | 21 |
| abstract_inverted_index.because | 32 |
| abstract_inverted_index.between | 147 |
| abstract_inverted_index.enforce | 39 |
| abstract_inverted_index.equally | 157 |
| abstract_inverted_index.exactly | 102 |
| abstract_inverted_index.minimax | 125 |
| abstract_inverted_index.optimal | 126, 134 |
| abstract_inverted_index.outputs | 94 |
| abstract_inverted_index.problem | 139 |
| abstract_inverted_index.results | 135, 155 |
| abstract_inverted_index.studies | 2 |
| abstract_inverted_index.$C,α>0$ | 117 |
| abstract_inverted_index.E}\|_2$, | 115 |
| abstract_inverted_index.E}\|_2$. | 131 |
| abstract_inverted_index.Toeplitz | 12, 64, 96 |
| abstract_inverted_index.absolute | 119 |
| abstract_inverted_index.analysis | 143 |
| abstract_inverted_index.applying | 53 |
| abstract_inverted_index.low-rank | 11 |
| abstract_inverted_index.matrices | 161 |
| abstract_inverted_index.problems | 28, 150 |
| abstract_inverted_index.provides | 144 |
| abstract_inverted_index.spectral | 58, 152 |
| abstract_inverted_index.{\mathbb | 68, 84 |
| abstract_inverted_index.algorithm | 56, 93 |
| abstract_inverted_index.arbitrary | 81 |
| abstract_inverted_index.corrupted | 10, 78 |
| abstract_inverted_index.difficult | 37 |
| abstract_inverted_index.directly. | 40 |
| abstract_inverted_index.guarantee | 123 |
| abstract_inverted_index.optimally | 51 |
| abstract_inverted_index.problems: | 6 |
| abstract_inverted_index.satisfies | 72 |
| abstract_inverted_index.E}\|_2\leq | 90 |
| abstract_inverted_index.Recovering | 8 |
| abstract_inverted_index.applicable | 158 |
| abstract_inverted_index.assumption | 75 |
| abstract_inverted_index.constants. | 120 |
| abstract_inverted_index.recovering | 16 |
| abstract_inverted_index.regularity | 74 |
| abstract_inverted_index.structural | 34 |
| abstract_inverted_index.structured | 4 |
| abstract_inverted_index.C}^{n\times | 69, 85 |
| abstract_inverted_index.challenging | 31 |
| abstract_inverted_index.connections | 146 |
| abstract_inverted_index.constraints | 35 |
| abstract_inverted_index.efficiently | 49 |
| abstract_inverted_index.estimation. | 59, 153 |
| abstract_inverted_index.performance | 122 |
| abstract_inverted_index.superficial | 163 |
| abstract_inverted_index.observation. | 26 |
| abstract_inverted_index.quantitative | 145 |
| abstract_inverted_index.${\boldsymbol | 66, 82 |
| abstract_inverted_index.approximation | 5 |
| abstract_inverted_index.Gradient-MUSIC | 55 |
| abstract_inverted_index.\|{\boldsymbol | 114 |
| abstract_inverted_index.modifications. | 164 |
| abstract_inverted_index.$\|{\boldsymbol | 89, 106, 130 |
| abstract_inverted_index.computationally | 30 |
| abstract_inverted_index.$\widehat{\boldsymbol | 98 |
| abstract_inverted_index.T}-\widehat{\boldsymbol | 107 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 2 |
| citation_normalized_percentile |