What Can Be Recovered Under Sparse Adversarial Corruption? Assumption-Free Theory for Linear Measurements

Abdeldjalil A\"issa-El-Bey; Alexandre Reiffers-Masson; Gugan Thoppe; Vishal Halder

arxiv: 2510.24215 · v4 · submitted 2025-10-28 · 💻 cs.IT · cs.LG· eess.SP· math.IT

What Can Be Recovered Under Sparse Adversarial Corruption? Assumption-Free Theory for Linear Measurements

Vishal Halder , Alexandre Reiffers-Masson , Abdeldjalil A\"issa-El-Bey , Gugan Thoppe This is my paper

Pith reviewed 2026-05-18 03:37 UTC · model grok-4.3

classification 💻 cs.IT cs.LGeess.SPmath.IT

keywords sparse adversarial corruptionlinear measurementsrobust recoveryrowspace intersectionkernel characterizationl0 minimizationphase transitionnetwork tomography

0 comments

The pith

For any measurement matrix A, the information about x* that survives any q-sparse adversarial corruption e is exactly the affine space x* plus the kernel of the orthogonal projection U onto the intersection of all rowspaces after deleting 2

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shifts focus from seeking conditions that force exact recovery of x* to characterizing exactly what partial information about x* remains available in y = A x* + e no matter how an adversary chooses a q-sparse e. It proves that this robust information is the affine subspace x* + ker(U), where U is the orthogonal projection onto the intersection of the row spaces of every possible submatrix of A that keeps all but 2q rows. The same characterization shows that every vector minimizing the number of nonzero residuals ||y - A x||_0 lies inside this subspace. For Gaussian random A the result produces a sharp phase transition: depending on dimensions and q, either full recovery occurs or only the trivial information survives.

Core claim

The robust information recoverable from y despite q-sparse e is precisely x* + ker(U), where U is the orthogonal projection onto the intersection of rowspaces of all submatrices of A obtained by deleting 2q rows. Every x that minimizes ||y - A x||_0 belongs to x* + ker(U).

What carries the argument

The orthogonal projection U onto the intersection of the rowspaces of every submatrix of A formed by deleting exactly 2q rows; this U isolates the measurement directions that remain consistent for every possible choice of q corruptions.

If this is right

Exact recovery of x* occurs precisely when ker(U) is the zero vector.
The l0-minimization problem itself yields vectors inside the recoverable set without needing to know e.
For i.i.d. Gaussian A a sharp threshold on m, n, and q separates regimes of exact recovery from regimes of only trivial recovery.
The same U can be used to design or analyze measurement matrices for applications such as robust network tomography.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Matrices with repeated or linearly dependent rows can be deliberately chosen to enlarge the dimension of ker(U) and thereby protect more information against a given q.
An efficient approximation to U might be obtained by sampling a modest number of 2q-row deletions instead of enumerating all combinations.
The same geometric construction of intersecting rowspaces after controlled deletions could be examined for nonlinear sensing models where rowspace language is replaced by tangent spaces.

Load-bearing premise

The intersection of those rowspaces after every deletion of exactly 2q rows must isolate precisely the directions that cannot be altered by any q-sparse support.

What would settle it

For a concrete small A, chosen x*, and explicit q-sparse e, compute the set of all l0-minimizers of ||y - A x||_0 and check whether it lies strictly inside or outside the predicted affine space x* + ker(U).

read the original abstract

Recovery from linear measurements under sparse adversarial corruption is typically formulated as an exact-recovery problem: one seeks structural conditions on $A$ (e.g., the restricted isometry property) that guarantee unique recovery of $x^\star$ from $y = A x^\star + e$ with $\left\lVert e \right\rVert_0 \leq q$. However, in practice, these conditions are rarely met and are hard to verify, and so the existing guarantees provide no guidance once exact recovery fails. This limitation obscures even simple robustness phenomena -- for instance, repeated rows in $A$ can preserve nontrivial information about $x^\star$ under sparse corruption. In this paper, we address the more general question: for arbitrary $A \in \mathbb{R}^{m \times n}$, what information about $x^\star$ remains robust in $y$ despite any $q$-sparse adversarial corruption $e$? We show that the robust information is precisely $x^\star + \ker(U)$, where $U$ is the orthogonal projection onto the intersection of rowspaces of all submatrices of $A$ obtained by deleting $2q$ rows. This characterization clarifies, for each sparsity level $q$, how the row structure of $A$ determines whether a $q$-sparse $e$ allows exact, partial, or only trivial recovery, thereby extending the standard exact-recovery framework. We further prove that every $x$ that minimizes $\left\lVert y - A x \right\rVert_0$ belongs to $x^\star + \ker(U)$, yielding a constructive approach to recover this set. For i.i.d. Gaussian $A$, we show a sharp phase transition: depending on $m$, $n$, and $q$, either exact recovery holds or no nontrivial recovery is possible. We sketch two applications: robust network tomography and signal reconstruction from oversampled DCT measurements.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a direct geometric characterization of what survives q-sparse adversarial corruption for any matrix A, without RIP or similar assumptions.

read the letter

The main point is that for arbitrary A the recoverable information about x* is exactly the coset x* + ker(U), where U is the orthogonal projection onto the intersection of all rowspaces obtained by deleting 2q rows. They also show that every l0-minimizer of the corrupted system lies in this set, and that Gaussian matrices exhibit a sharp phase transition between exact recovery and no nontrivial recovery at all. This replaces the usual exact-recovery framework with a precise description of partial recovery that applies even when standard conditions fail, such as in network tomography or oversampled DCT cases with repeated rows. The linear-algebra construction is new and explains robustness phenomena that prior work left opaque. The containment of l0-minimizers adds a constructive element that could be useful in practice. The Gaussian phase transition is stated explicitly and appears internally consistent with the geometric objects defined. The main soft spot is whether the 2q-deletion intersection isolates the robust directions exactly when A has linear dependencies among its rows. If the intersection is larger than the true robust subspace because of repeated or dependent rows, ker(U) shrinks too much and the claimed equality may not hold for every possible A. The abstract presents the argument as direct linear algebra with no fitting or circularity, but the full derivation would need checking on this point to confirm necessity and sufficiency of exactly 2q for arbitrary matrices. This work is for people in compressed sensing or robust recovery who want to analyze what information remains when exact recovery is impossible. A reader focused on assumption-free guarantees or geometric views of robustness would get concrete value from the characterization and the phase transition. It deserves a serious referee because the central claim is sharp, the objects are well-defined, and the Gaussian result is falsifiable.

Referee Report

1 major / 0 minor

Summary. The paper claims that for arbitrary A in R^{m x n}, the information about x* robust to any q-sparse adversarial e in y = A x* + e is exactly the coset x* + ker(U), where U is the orthogonal projection onto the intersection of rowspaces of all submatrices of A obtained by deleting exactly 2q rows. It further proves that every minimizer of ||y - A x||_0 lies in this set, and for i.i.d. Gaussian A there is a sharp phase transition between exact recovery and only trivial recovery, depending on m, n, q. Applications to robust network tomography and oversampled DCT reconstruction are sketched.

Significance. If the characterization holds, the result supplies an assumption-free geometric description of partial robustness under sparse corruption, explaining why repeated rows in A can preserve nontrivial information even when exact recovery fails. The containment of l0-minimizers inside the claimed coset is constructive, and the sharp Gaussian phase transition is a strong, falsifiable prediction. These features extend the standard RIP-based exact-recovery framework to the regime where structural conditions on A are not met.

major comments (1)

The central claim equates the recoverable set to x* + ker(U) for arbitrary A, with U the ortho projection onto ∩ rowspace(A_S) over all |S| = m-2q. This requires that any direction v orthogonal to that intersection is affected by some q-sparse e. When rows of A are linearly dependent or repeated, the rowspace intersection may be strictly larger than the true robust subspace, making ker(U) too small and the equality fail; the manuscript does not supply an explicit reduction or counterexample verifying that 2q (rather than q or another multiple) is necessary and sufficient for arbitrary, non-generic A. This is load-bearing for the assumption-free characterization stated in the abstract.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for identifying a point that merits explicit clarification. The characterization holds for arbitrary A; the factor 2q is both necessary and sufficient, as shown by a simple explicit construction with repeated rows that we will add to the manuscript.

read point-by-point responses

Referee: The central claim equates the recoverable set to x* + ker(U) for arbitrary A, with U the ortho projection onto ∩ rowspace(A_S) over all |S| = m-2q. This requires that any direction v orthogonal to that intersection is affected by some q-sparse e. When rows of A are linearly dependent or repeated, the rowspace intersection may be strictly larger than the true robust subspace, making ker(U) too small and the equality fail; the manuscript does not supply an explicit reduction or counterexample verifying that 2q (rather than q or another multiple) is necessary and sufficient for arbitrary, non-generic A. This is load-bearing for the assumption-free characterization stated in the abstract.

Authors: The factor of 2q is required because a nonzero direction v can be rendered consistent with two q-sparse corruptions (one for each of two candidate signals) precisely when the support of Av has cardinality at most 2q. Consequently, the intersection is taken over all submatrices obtained by deleting 2q rows so that the surviving rowspace consists exactly of those linear functionals that cannot be altered by any admissible adversarial corruption. This geometric argument uses only the definition of rowspace and imposes no genericity or independence assumptions on A. To see that 2q is tight for arbitrary matrices, consider the following explicit example. Let A consist of exactly 2q identical rows equal to a vector a (and no other rows). There exists a submatrix obtained by deleting these 2q rows whose rowspace does not contain a; hence a does not lie in the intersection, U is the zero projection, and the claimed coset is the entire space. This is correct: an adversary may corrupt any q of the entries, setting them to an arbitrary value b while leaving the remaining q entries equal to a·x*. The resulting observations contain q copies of a·x* and q copies of b, so a·x* cannot be uniquely recovered. By contrast, if A contains 2q+1 identical copies of a, every submatrix after deletion of 2q rows retains at least one copy, a belongs to the intersection, and the functional is robustly recovered. The same construction shows that replacing 2q by q (or any other multiple) would be incorrect. Because the manuscript’s proofs that every ℓ0-minimizer lies inside the coset and that the coset is precisely the robust information rely only on this rowspace geometry, they apply verbatim to matrices with repeated or linearly dependent rows. We will insert the above example together with the 2q revision: yes

Circularity Check

0 steps flagged

No circularity: direct linear-algebra characterization of robust information via explicit rowspace construction

full rationale

The paper defines U explicitly as the orthogonal projection onto the intersection of rowspaces of all (m-2q)-row submatrices of A, then proves that the recoverable set equals x* + ker(U) and that minimizers of ||y - Ax||_0 lie in this set. This is a self-contained geometric argument on kernels and rowspaces for arbitrary A; no parameter is fitted to data and then renamed as a prediction, no self-citation chain is load-bearing for the central claim, and the 2q deletion count is part of the stated construction rather than smuggled in or justified only by prior work of the same authors. The derivation therefore does not reduce to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on standard facts from linear algebra (rowspace intersections, orthogonal projections, kernels) with no free parameters fitted to data, no ad-hoc invented entities, and no domain-specific axioms beyond the definition of q-sparse adversarial corruption.

axioms (1)

standard math Standard properties of row spaces, orthogonal projections, and kernels in finite-dimensional real vector spaces
Invoked to define U and to equate the robust information with x^* + ker(U)

pith-pipeline@v0.9.0 · 5915 in / 1672 out tokens · 41036 ms · 2026-05-18T03:37:17.262074+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

the robust information is precisely x^* + ker(U), where U is the orthogonal projection onto the intersection of rowspaces of all submatrices of A obtained by deleting 2q rows
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

S_A^q := {v ∈ R^n : ||A v||_0 ≤ 2q}

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages · 1 internal anchor

[1]

INTRODUCTION Linear measurements are foundational to signal processing and machine learning, yet they are highly susceptible to ad- versarial corruptions [1–3]. In this paper, we focus on a spe- cific corruption model, calledsparse adversarial corruption, which models critical real-world scenarios, such as compro- mised sensors in control systems and smar...

work page
[2]

What Can Be Recovered Under Sparse Adversarial Corruption? Assumption-Free Theory for Linear Measurements

NOTATION We denote scalars by lowercase lettersq, m, nand sets by uppercase lettersS, T. We denote vector spaces by cal- ligraphic lettersR,S, and possibly nonlinear functions by script lettersG. We write vectors as bold lowercase letters x,yand matrices as bold uppercase lettersA,B,U. For a matrixA, we writerowspan(A)for the vector space spanned by its r...

work page internal anchor Pith review Pith/arXiv arXiv 2025
[3]

We begin by defining the notion of the ambiguity set, which captures all differences of signal pairs that can be explained byq-sparse corruptions

MAIN RESULTS This section is dedicated to the main theoretical results of our paper. We begin by defining the notion of the ambiguity set, which captures all differences of signal pairs that can be explained byq-sparse corruptions. Formally, we have the following definition: Definition 1.ForA∈R m×n and integerq < m/2, define theambiguity setS A q :={v∈R n...

work page
[4]

ALGORITHM In this section, we introduce a computation scheme (Algorithm

work page
[5]

We also study its complexity

that takes as input the matrixAand an upper boundqon the number of adversarial measurements, and returns the robust orthogonal projection matrix, defined in Theorem 1. We also study its complexity. Algorithm 1Computing the robust orthogonal projector Require:A∈R m×n, integerq < m/2 Output:Orthogonal projectorUonto the robust subspaceT T⊆[m],|T|=m−2q rowsp...

work page
[6]

NUMERICAL ILLUSTRATIONS We illustrate our theoretical results with a concrete example and experimental simulations. Consider a network of five links, where each measurement corresponds to a path through the network and records the sum of the link values along that path (e.g., total delay or packet loss). The goal is to robustly recover key link properties...

work page
[7]

CONCLUSION We characterize the maximal recoverable information about an unknown signalx ⋆ from adversariallyq-sparse corrupted measurementsy=Ax ⋆ +e. This information corresponds to the inclusion-wise minimal solution set of signals, pre- ciselyx ⋆ + ker(U), whereUis the orthogonal projector onto the intersection of rowspaces of all submatrices ofA formed...

work page
[8]

Robust estimation of a location parame- ter,

Peter J Huber, “Robust estimation of a location parame- ter,”The Annals of Mathematical Statistics, vol. 35, no. 1, pp. 73–101, 1964

work page 1964
[9]

Least median of squares regres- sion,

Peter J Rousseeuw, “Least median of squares regres- sion,”Journal of the American statistical association, vol. 79, no. 388, pp. 871–880, 1984

work page 1984
[10]

Robust algorithms on adaptive inputs from bounded adversaries,

Yeshwanth Cherapanamjeri, Sandeep Silwal, David P Woodruff, Fred Zhang, Qiuyi Zhang, and Samson Zhou, “Robust algorithms on adaptive inputs from bounded adversaries,” inInternational Conference on Learning Representations. International Conference on Learning Representations, 2023

work page 2023
[11]

Safe and secure networked control systems under denial-of-service attacks,

Saurabh Amin, Alvaro A C ´ardenas, and S Shankar Sas- try, “Safe and secure networked control systems under denial-of-service attacks,” inInternational workshop on hybrid systems: computation and control. Springer, 2009, pp. 31–45

work page 2009
[12]

False data injection attacks against state estimation in electric power grids,

Yao Liu, Peng Ning, and Michael K Reiter, “False data injection attacks against state estimation in electric power grids,”ACM Transactions on Information and System Security (TISSEC), vol. 14, no. 1, pp. 1–33, 2011

work page 2011
[13]

Low-rank pos- itive semidefinite matrix recovery from corrupted rank- one measurements,

Yuanxin Li, Yue Sun, and Yuejie Chi, “Low-rank pos- itive semidefinite matrix recovery from corrupted rank- one measurements,”IEEE Transactions on Signal Pro- cessing, vol. 65, no. 2, pp. 397–408, 2016

work page 2016
[14]

Decoding by linear programming,

Emmanuel J Candes and Terence Tao, “Decoding by linear programming,”IEEE transactions on information theory, vol. 51, no. 12, pp. 4203–4215, 2005

work page 2005
[15]

Compressed sensing and best k-term approximation,

Albert Cohen, Wolfgang Dahmen, and Ronald DeVore, “Compressed sensing and best k-term approximation,” Journal of the American mathematical society, vol. 22, no. 1, pp. 211–231, 2009

work page 2009
[16]

Se- cure estimation and control for cyber-physical systems under adversarial attacks,

Hamza Fawzi, Paulo Tabuada, and Suhas Diggavi, “Se- cure estimation and control for cyber-physical systems under adversarial attacks,”IEEE Transactions on Auto- matic control, vol. 59, no. 6, pp. 1454–1467, 2014

work page 2014
[17]

Optimally sparse representation in general (nonorthogonal) dictionaries viaℓ 1 minimization,

David L Donoho and Michael Elad, “Optimally sparse representation in general (nonorthogonal) dictionaries viaℓ 1 minimization,”Proceedings of the National Academy of Sciences, vol. 100, no. 5, pp. 2197–2202, 2003

work page 2003
[18]

The computa- tional complexity of the restricted isometry property, the nullspace property, and related concepts in compressed sensing,

Andreas M Tillmann and Marc E Pfetsch, “The computa- tional complexity of the restricted isometry property, the nullspace property, and related concepts in compressed sensing,”IEEE Transactions on Information Theory, vol. 60, no. 2, pp. 1248–1259, 2013

work page 2013
[19]

Certifying the restricted isometry property is hard,

Afonso S Bandeira, Edgar Dobriban, Dustin G Mixon, and William F Sawin, “Certifying the restricted isometry property is hard,”IEEE transactions on information theory, vol. 59, no. 6, pp. 3448–3450, 2013

work page 2013
[20]

Approximately certifying the restricted isometry property is hard,

Jonathan Weed, “Approximately certifying the restricted isometry property is hard,”IEEE Transactions on Infor- mation Theory, vol. 64, no. 8, pp. 5488–5497, 2017

work page 2017
[21]

The fundamental theorem of linear al- gebra,

Gilbert Strang, “The fundamental theorem of linear al- gebra,”The American Mathematical Monthly, vol. 100, no. 9, pp. 848–855, 1993

work page 1993
[22]

Halmos,Finite-Dimensional Vector Spaces, Un- dergraduate Texts in Mathematics

Paul R. Halmos,Finite-Dimensional Vector Spaces, Un- dergraduate Texts in Mathematics. Springer New York, NY, 1958

work page 1958
[23]

Se- cure state-estimation for dynamical systems under active adversaries,

Hamza Fawzi, Paulo Tabuada, and Suhas Diggavi, “Se- cure state-estimation for dynamical systems under active adversaries,” in2011 49th annual allerton conference on communication, control, and computing (allerton). IEEE, 2011, pp. 337–344

work page 2011
[24]

Efficient identification of additive link metrics via network tomography,

Liang Ma, Ting He, Kin K Leung, Don Towsley, and Ananthram Swami, “Efficient identification of additive link metrics via network tomography,” in2013 IEEE 33rd International Conference on Distributed Comput- ing Systems. IEEE, 2013, pp. 581–590

work page 2013
[25]

Algorithms and hard- ness for robust subspace recovery,

Moritz Hardt and Ankur Moitra, “Algorithms and hard- ness for robust subspace recovery,” inConference on Learning Theory. PMLR, 2013, pp. 354–375

work page 2013
[26]

Online learning with adversaries: A differential-inclusion analysis,

Swetha Ganesh, Alexandre Reiffers-Masson, and Gu- gan Thoppe, “Online learning with adversaries: A differential-inclusion analysis,” in2023 62nd IEEE Con- ference on Decision and Control (CDC). IEEE, 2023, pp. 1288–1293

work page 2023

[1] [1]

INTRODUCTION Linear measurements are foundational to signal processing and machine learning, yet they are highly susceptible to ad- versarial corruptions [1–3]. In this paper, we focus on a spe- cific corruption model, calledsparse adversarial corruption, which models critical real-world scenarios, such as compro- mised sensors in control systems and smar...

work page

[2] [2]

What Can Be Recovered Under Sparse Adversarial Corruption? Assumption-Free Theory for Linear Measurements

NOTATION We denote scalars by lowercase lettersq, m, nand sets by uppercase lettersS, T. We denote vector spaces by cal- ligraphic lettersR,S, and possibly nonlinear functions by script lettersG. We write vectors as bold lowercase letters x,yand matrices as bold uppercase lettersA,B,U. For a matrixA, we writerowspan(A)for the vector space spanned by its r...

work page internal anchor Pith review Pith/arXiv arXiv 2025

[3] [3]

We begin by defining the notion of the ambiguity set, which captures all differences of signal pairs that can be explained byq-sparse corruptions

MAIN RESULTS This section is dedicated to the main theoretical results of our paper. We begin by defining the notion of the ambiguity set, which captures all differences of signal pairs that can be explained byq-sparse corruptions. Formally, we have the following definition: Definition 1.ForA∈R m×n and integerq < m/2, define theambiguity setS A q :={v∈R n...

work page

[4] [4]

ALGORITHM In this section, we introduce a computation scheme (Algorithm

work page

[5] [5]

We also study its complexity

that takes as input the matrixAand an upper boundqon the number of adversarial measurements, and returns the robust orthogonal projection matrix, defined in Theorem 1. We also study its complexity. Algorithm 1Computing the robust orthogonal projector Require:A∈R m×n, integerq < m/2 Output:Orthogonal projectorUonto the robust subspaceT T⊆[m],|T|=m−2q rowsp...

work page

[6] [6]

NUMERICAL ILLUSTRATIONS We illustrate our theoretical results with a concrete example and experimental simulations. Consider a network of five links, where each measurement corresponds to a path through the network and records the sum of the link values along that path (e.g., total delay or packet loss). The goal is to robustly recover key link properties...

work page

[7] [7]

CONCLUSION We characterize the maximal recoverable information about an unknown signalx ⋆ from adversariallyq-sparse corrupted measurementsy=Ax ⋆ +e. This information corresponds to the inclusion-wise minimal solution set of signals, pre- ciselyx ⋆ + ker(U), whereUis the orthogonal projector onto the intersection of rowspaces of all submatrices ofA formed...

work page

[8] [8]

Robust estimation of a location parame- ter,

Peter J Huber, “Robust estimation of a location parame- ter,”The Annals of Mathematical Statistics, vol. 35, no. 1, pp. 73–101, 1964

work page 1964

[9] [9]

Least median of squares regres- sion,

Peter J Rousseeuw, “Least median of squares regres- sion,”Journal of the American statistical association, vol. 79, no. 388, pp. 871–880, 1984

work page 1984

[10] [10]

Robust algorithms on adaptive inputs from bounded adversaries,

Yeshwanth Cherapanamjeri, Sandeep Silwal, David P Woodruff, Fred Zhang, Qiuyi Zhang, and Samson Zhou, “Robust algorithms on adaptive inputs from bounded adversaries,” inInternational Conference on Learning Representations. International Conference on Learning Representations, 2023

work page 2023

[11] [11]

Safe and secure networked control systems under denial-of-service attacks,

Saurabh Amin, Alvaro A C ´ardenas, and S Shankar Sas- try, “Safe and secure networked control systems under denial-of-service attacks,” inInternational workshop on hybrid systems: computation and control. Springer, 2009, pp. 31–45

work page 2009

[12] [12]

False data injection attacks against state estimation in electric power grids,

Yao Liu, Peng Ning, and Michael K Reiter, “False data injection attacks against state estimation in electric power grids,”ACM Transactions on Information and System Security (TISSEC), vol. 14, no. 1, pp. 1–33, 2011

work page 2011

[13] [13]

Low-rank pos- itive semidefinite matrix recovery from corrupted rank- one measurements,

Yuanxin Li, Yue Sun, and Yuejie Chi, “Low-rank pos- itive semidefinite matrix recovery from corrupted rank- one measurements,”IEEE Transactions on Signal Pro- cessing, vol. 65, no. 2, pp. 397–408, 2016

work page 2016

[14] [14]

Decoding by linear programming,

Emmanuel J Candes and Terence Tao, “Decoding by linear programming,”IEEE transactions on information theory, vol. 51, no. 12, pp. 4203–4215, 2005

work page 2005

[15] [15]

Compressed sensing and best k-term approximation,

Albert Cohen, Wolfgang Dahmen, and Ronald DeVore, “Compressed sensing and best k-term approximation,” Journal of the American mathematical society, vol. 22, no. 1, pp. 211–231, 2009

work page 2009

[16] [16]

Se- cure estimation and control for cyber-physical systems under adversarial attacks,

Hamza Fawzi, Paulo Tabuada, and Suhas Diggavi, “Se- cure estimation and control for cyber-physical systems under adversarial attacks,”IEEE Transactions on Auto- matic control, vol. 59, no. 6, pp. 1454–1467, 2014

work page 2014

[17] [17]

Optimally sparse representation in general (nonorthogonal) dictionaries viaℓ 1 minimization,

David L Donoho and Michael Elad, “Optimally sparse representation in general (nonorthogonal) dictionaries viaℓ 1 minimization,”Proceedings of the National Academy of Sciences, vol. 100, no. 5, pp. 2197–2202, 2003

work page 2003

[18] [18]

The computa- tional complexity of the restricted isometry property, the nullspace property, and related concepts in compressed sensing,

Andreas M Tillmann and Marc E Pfetsch, “The computa- tional complexity of the restricted isometry property, the nullspace property, and related concepts in compressed sensing,”IEEE Transactions on Information Theory, vol. 60, no. 2, pp. 1248–1259, 2013

work page 2013

[19] [19]

Certifying the restricted isometry property is hard,

Afonso S Bandeira, Edgar Dobriban, Dustin G Mixon, and William F Sawin, “Certifying the restricted isometry property is hard,”IEEE transactions on information theory, vol. 59, no. 6, pp. 3448–3450, 2013

work page 2013

[20] [20]

Approximately certifying the restricted isometry property is hard,

Jonathan Weed, “Approximately certifying the restricted isometry property is hard,”IEEE Transactions on Infor- mation Theory, vol. 64, no. 8, pp. 5488–5497, 2017

work page 2017

[21] [21]

The fundamental theorem of linear al- gebra,

Gilbert Strang, “The fundamental theorem of linear al- gebra,”The American Mathematical Monthly, vol. 100, no. 9, pp. 848–855, 1993

work page 1993

[22] [22]

Halmos,Finite-Dimensional Vector Spaces, Un- dergraduate Texts in Mathematics

Paul R. Halmos,Finite-Dimensional Vector Spaces, Un- dergraduate Texts in Mathematics. Springer New York, NY, 1958

work page 1958

[23] [23]

Se- cure state-estimation for dynamical systems under active adversaries,

Hamza Fawzi, Paulo Tabuada, and Suhas Diggavi, “Se- cure state-estimation for dynamical systems under active adversaries,” in2011 49th annual allerton conference on communication, control, and computing (allerton). IEEE, 2011, pp. 337–344

work page 2011

[24] [24]

Efficient identification of additive link metrics via network tomography,

Liang Ma, Ting He, Kin K Leung, Don Towsley, and Ananthram Swami, “Efficient identification of additive link metrics via network tomography,” in2013 IEEE 33rd International Conference on Distributed Comput- ing Systems. IEEE, 2013, pp. 581–590

work page 2013

[25] [25]

Algorithms and hard- ness for robust subspace recovery,

Moritz Hardt and Ankur Moitra, “Algorithms and hard- ness for robust subspace recovery,” inConference on Learning Theory. PMLR, 2013, pp. 354–375

work page 2013

[26] [26]

Online learning with adversaries: A differential-inclusion analysis,

Swetha Ganesh, Alexandre Reiffers-Masson, and Gu- gan Thoppe, “Online learning with adversaries: A differential-inclusion analysis,” in2023 62nd IEEE Con- ference on Decision and Control (CDC). IEEE, 2023, pp. 1288–1293

work page 2023