Minimum-norm Sparse Perturbations for Opacity in Linear Systems
Opacity is a notion that describes an eavesdropper's inability to estimate a system's 'secret' states by observing the system's outputs. In this paper, we propose algorithms to compute the minimum sparse perturbation to be added to a system to make its initial states opaque. For these perturbations, we consider two sparsity constraints - structured and affine. We develop an algorithm to compute the global minimum-norm perturbation for the structured case. For the affine case, we use the global minimum solution of the structured case as initial point to compute a local minimum. Empirically, this local minimum is very close to the global minimum. We demonstrate our results via a running example.
Code (1)
Similar Papers 제목 키워드 기반
Minimum Norm Method for Linear and Planar Sparse Arrays
Coprime and nested arrays are sparse arrays with enhanced degrees of freedom, which can be exploited in direction of arrival estimation using algorithms such as product processing, min processing, and MUSIC. This paper a…
Direction of Arrival EstimationOn the Landscape of Sparse Linear Networks
Network pruning, or sparse network has a long history and practical significance in modern applications. Although the loss functions of neural networks may yield bad landscape due to non-convexity, we focus on linear act…
Network PruningSpectral-transport stability and benign overfitting for minimum norm interpolation
Benign overfitting describes the ability of minimum norm interpolating estimators to generalize despite fitting noisy data exactly. Existing characterizations depend on delicate spectral functionals of the population cov…
Foolish Crowds Support Benign Overfitting
We prove a lower bound on the excess risk of sparse interpolating procedures for linear regression with Gaussian data in the overparameterized regime. We apply this result to obtain a lower bound for basis pursuit (the m…
regressionMinimum $\ell_{1}$-norm interpolators: Precise asymptotics and multiple descent
An evolving line of machine learning works observe empirical evidence that suggests interpolating estimators -- the ones that achieve zero training error -- may not necessarily be harmful. This paper pursues theoretical …