Cone Rayleigh Levels: Finite Perturbations and Certified Control

Yavdat Sh. Il'yasov; Nur F. Valeev

cs.LGAug 27, 2026

Cone Rayleigh Levels: Finite Perturbations and Certified Control

Authors: Yavdat Sh. Il'yasov, Nur F. Valeev

Organizations: Institute of Mathematics with Computing Centre, Ufa Federal Research Centre of the Russian Academy of Sciences, 112 Chernyshevsky St., Ufa 450008, Russia.

Abstract

We study the reuse of positive trial profiles under finite perturbations of nonsymmetric matrix pencils B-λG. The lower and upper cone Rayleigh levels need not coincide and are defined without requiring positive eigenvectors. In the positive orthant with positive diagonal $G$ , we derive computable perturbation bounds and determine the exact worst-case trial gap over prescribed independent entrywise perturbation classes. This yields the largest uniform radius meeting a given trial-gap tolerance for fixed profiles, certifying trial-value accuracy without recomputation. Experiments on a nonnegative operator and five signed matrices compare sufficient and optimal radii, directional thresholds, and cold- and warm-start recomputation. Several signed cases exhibit severely limited uniform profile reuse despite the optimality of the radius. Exact rational checks verify the reported bounds and worst-case constructions for stored numerical inputs. A finite-budget linear program and differentiable constraints illustrate applications to verified control and learning.

Figures & tables

Operator	Direction	$r_{\rm cert}$	$r_{*}$	$r_{\rm ret}$	$r_{*}/r_{\rm cert}$	$r_{\rm ret}/r_{*}$
$B$	Local	$6.545\times 10^{-5}$	$6.545\times 10^{-5}$	$9.790\times 10^{-5}$	$1.000$	$1.496$
$B$	Rank two	$1.030\times 10^{-5}$	$1.061\times 10^{-5}$	$1.381\times 10^{-4}$	$1.031$	$13.017$
$M_{1}$	Local	$4.062\times 10^{-5}$	$4.062\times 10^{-5}$	$5.204\times 10^{-5}$	$1.000$	$1.281$
$M_{1}$	Rank two	$1.570\times 10^{-11}$	$1.036\times 10^{-5}$	$1.299\times 10^{-4}$	$6.600\times 10^{5}$	$12.536$
$M_{2}$	Local	$3.528\times 10^{-5}$	$3.528\times 10^{-5}$	$8.461\times 10^{-5}$	$1.000$	$2.398$
$M_{2}$	Rank two	$2.312\times 10^{-10}$	$2.551\times 10^{-10}$	$2.687\times 10^{-9}$	$1.103$	$10.530$

Table 1: Sufficient and optimal uniform trial-gap radii, and thresholds along the selected directions, for

G=I

and

\varepsilon=10^{-4}

. The mask is

M=|H|

in each case.

r_{*}

is optimal over all independent signed entrywise perturbations satisfying

|E|\leq rM

; the rank-two designation refers to the selected direction, not to this full mask class. Displayed values are rounded from exact rational calculations for the stored numerical inputs.

Operator	$\min_{i}u_{i}$	$\max_{i}u_{i}$	$\min_{j}v_{j}$	$\max_{j}v_{j}$	$\zeta(u,v)$
$B$	$3.052\times 10^{-3}$	$2.155\times 10^{-2}$	$2.160\times 10^{-3}$	$1.930\times 10^{-2}$	$1.119\times 10^{-1}$
$M_{1}$	$2.207\times 10^{-6}$	$2.125\times 10^{-2}$	$1.291\times 10^{-9}$	$2.257\times 10^{-2}$	$5.721\times 10^{-8}$
$M_{2}$	$3.983\times 10^{-8}$	$2.063\times 10^{-2}$	$1.438\times 10^{-7}$	$1.042\times 10^{-1}$	$1.381\times 10^{-6}$
$M_{3}$	$5.284\times 10^{-8}$	$2.370\times 10^{-2}$	$2.000\times 10^{-7}$	$6.914\times 10^{-2}$	$2.230\times 10^{-6}$
$M_{4}$	$3.121\times 10^{-8}$	$2.499\times 10^{-2}$	$1.740\times 10^{-7}$	$1.283\times 10^{-1}$	$1.249\times 10^{-6}$
$M_{5}$	$1.331\times 10^{-7}$	$2.427\times 10^{-2}$	$1.971\times 10^{-7}$	$3.331\times 10^{-2}$	$5.483\times 10^{-6}$

Table 2: Component ranges of the retained baseline profiles, normalized by

\mathbf{1}^{T}u=\mathbf{1}^{T}v=1

. The balance indicator

\zeta

is defined in the text; smaller values indicate more uneven components. Each pair is used for both perturbation directions in Table 1 . Values are rounded from the stored numerical profiles.

Figure 1: Retained-profile gaps and perturbation bounds for the nonnegative reference operator

B

and signed Direction 4 under local and rank-two perturbations. The horizontal coordinate is

t/r_{\rm ret}

, where

r_{\rm ret}

is the numerically determined threshold for the retained gap along the selected direction. Curves show the mask bound

D_{A_{0}}+t(\alpha_{|H|}+\beta_{|H|})

, the directional bound

\Delta_{tH}

, and the retained gap computed from the affine component ratios. Circles show rationally verified gaps for the stored rounded operators

\widetilde{A}=\operatorname{fl}(A_{0}+tH)

. The horizontal line is the tolerance

\varepsilon=10^{-4}

; the vertical dotted line marks

r_{\rm cert}/r_{\rm ret}

. The directional bound is nearly indistinguishable from the retained gap in the two panels for

B

. Axis ranges differ between panels.

Operator	Cold (ms)	Warm (ms)	Paired speedup
$B$	51.44	41.20	1.24
$M_{1}$	93.56	76.94	1.20
$M_{2}$	91.29	75.31	1.21
$M_{3}$	69.03	47.07	1.42
$M_{4}$	58.78	47.19	1.23
$M_{5}$	93.83	73.95	1.28

Table 3: Profile recomputation on

16

cases per operator. Times are medians; speedup is the median of paired cold/warm time ratios.

Figure 2: Verified intervals for the lower and upper trial-value errors of retained profiles for

B

and Direction 4. Markers are interval midpoints; error bars display the lower and upper bounds in ( 6.4 ), obtained using the independently recomputed profiles. These are deterministic enclosures, not statistical confidence intervals. Endpoints are displayed as floating-point approximations of the exact rational bounds for the stored operators. Lines connect sampled amplitudes only as visual guides. The horizontal line is

\varepsilon=10^{-4}

. The horizontal axis is logarithmic; the vertical axis is logarithmic above

10^{-8}

and linear near zero. Axis ranges differ between panels.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Direction	$\rho$	$z$ -LP	$\gamma$ -LP	Eigenvalue	FD
1	0.20	0.627796	0.627796	1.017332	1.026034
2	0.20	0.816841	0.717112	1.218438	2.526045
3	0.35	0.757443	0.695128	0.978708	1.729301
4	0.20	0.927790	0.723088	1.092553	2.346158
5	0.40	0.771523	0.719848	1.495004	1.686692

Appendix

Table 4: Observed upper-estimate reductions at

\eta=0.04

, in units of

10^{-3}

Operator	$z$ -LP	$\gamma$ -LP	Eigenvalue	FD
$M_{1}$	0.627636	0.627636	1.017019	1.025693
$M_{2}$	0.816422	0.716728	1.218014	2.525667
$M_{3}$	0.757108	0.694880	0.978454	1.729029
$M_{4}$	0.927394	0.722710	1.092216	2.345754
$M_{5}$	0.771161	0.719487	1.494578	1.686322

Appendix

Table 5: Verified decrease margins after common profile refinement at

\eta=0.04

, in units of

10^{-3}

. Values are rounded displays of the exact rational margins

m_{\rm best}(h)

Method	$10^{3}m_{\rm fixed}$	$10^{3}m_{\rm best}$	Refinement	Exact check
$z$ -LP	0.926651	0.927394	124.67	46.27
$\gamma$ -LP	0.721932	0.722710	120.84	45.97
Eigenvalue	-0.001100	1.092216	57.49	45.42
FD	-0.001100	2.345754	133.44	52.45

Appendix

Table 6: Direction 4 at

\eta=0.04

: fixed-profile and refined verification. Margins are in units of

10^{-3}

; times are in milliseconds. Refinement times are medians of three repetitions; exact-check times are measured once and include feasibility and both trial upper bounds. Baseline preparation is excluded.

Explore similar work

Well-Conditioned Oblivious Perturbations in Linear Space
Apr 25, 2026Shabarish Chenakkod, Michał Dereziński, Xiaoyu Dong +1
University of Michigan, Ann Arbor, MI, USA · National University of Singapore, Singapore
Probabilistic Analysis of Least Squares, Orthogonal Projection, and QR Factorization Algorithms Subject to Gaussian Noise
Sep 27, 2024Ali Lotfi, Julien Langou, Mohammad MeysamiSpectral Norm Singular Value Decomposition
Department of Computer Science, University of Saskatchewan, Saskatoon, SK S7N 5A2, Canada · Department of Applied Mathematics, University of Colorado Denver, Denver, Colorado2026 80201, USA · Department of Mathematics, The University of Tulsa, Tulsa, OK 74104, USA
Horizon-Uniform Sensitivity Certificates for Finite-Horizon Pontryagin Systems
Jun 16, 2026Pyuyi Chufeng Huang, Zikang Song, Xingshu ChenLyapunov Function Optimal Control
School of Cyber Science and Engineering, Sichuan University, Chengdu, Sichuan, China · School of Mathematics, Sichuan University, Chengdu, Sichuan, China

Apr 25, 2026, cs.DSJ/K move · Enter open · S save

Well-Conditioned Oblivious Perturbations in Linear Space

Shabarish Chenakkod, Michał Dereziński, Xiaoyu Dong, Mark Rudelson

University of Michigan, Ann Arbor, MI, USA · National University of Singapore, Singapore

Open paper AskPDF arXiv

Perturbing a deterministic

n

-dimensional matrix with small Gaussian noise is a cornerstone of smoothed analysis of algorithms [Spielman and Teng, JACM 2004], as it reduces the condition number of the input to

O(n)

, and with it the complexity of many matrix algorithms. However, when deployed algorithmically, these perturbations are expensive due to the cost of generating and storing

n^2

Gaussian random variables. We propose a perturbation that requires generating and storing

O(n)

random numbers in

O(\log n)

bits of precision, and reduces the condition number of any deterministic matrix to

O(n)

, matching Gaussian perturbations. Our result in particular implies a better complexity for the perturbed conjugate gradient algorithm, showing that we can solve an

n\times n

linear system in linear space to within an arbitrarily small constant backward error using

O(n)

matrix-vector products. In our construction, we introduce the concept of a pattern matrix, which is a dense deterministic matrix that maps all sparse vectors into dense vectors, and we combine it with a sparse perturbation whose entries are dependent and located in a non-uniform fashion. In order to analyze this construction, we develop new techniques for lower bounding the smallest singular value of a random matrix with dependent entries.

Abstract

Explore similar work

Well-Conditioned Oblivious Perturbations in Linear Space

Probabilistic Analysis of Least Squares, Orthogonal Projection, and QR Factorization Algorithms Subject to Gaussian Noise

Horizon-Uniform Sensitivity Certificates for Finite-Horizon Pontryagin Systems