0
$\begingroup$

I posted this question some time ago here. I started a bounty for it and received an answer which helped me a lot. However, I still have some issues I want to discuss regarding it. Unfortunately I can't contact the contributor that answered before, so I decided to ask a different question. Through this question I will be referring to the answer I received here just as the "answer".

The main issue summary is the following: I have $m<n$ real $n\times n$ positive definite matrices $P_1,\dotsc,P_m$. These define ellipsoids $E_i=\{x\in\mathbb{R}^n\mathrel:x^TP_ix=1\}$. I'm interested in the points that lie in the intersection of all these ellipsoids (let's call it $E\mathrel{:=}\bigcap_{i=1}^mE_i$ for short). A point $x$ is non regular if

  • $x\in E$.
  • The vectors $\{P_1x,\dotsc,P_mx\}$ are linearly dependent.

The problem is to show that if we make the change $P_i\leftarrow P_i+\epsilon_i$ with $\epsilon_i$ a random matrix with elements uniformly distributed in $[-\epsilon,\epsilon]$ (or some other distribution if desired), the probability of a point $x\in E$ to be nonregular is 0. Or equivalently that $x$ is "regular" almost surely for any $\epsilon>0$.

In the previous question, a contributor considered slightly different random matrices $$\tilde{\epsilon}_{i}=\epsilon_{i}+s_{i}I_{n}$$ where $s_{i}$ independent random variable in $[-\epsilon,\epsilon]$ with continuous density and $I_{n}$ the identity matrix. Then we can write $$x\in E_{i}(\epsilon)=\{x\in\mathbb{R}^{n}:s_{i}=\frac{1}{\lVert x\rVert^{2}}(1-x^{T}(P_i+\epsilon_{i})x)\}.$$

The contributor claimed that we decoupled the two events: ${x\in E(\epsilon)}$ is a random event that depends on the variable $s_{i}$, whereas $L_{\epsilon}(x):=\{(P_{1}+\epsilon_{1})x,\dotsc,(P_{m}+\epsilon_{m})x\text{ linearly independent}\}$ is a random event that depends on $\epsilon_i$. Then proceeded to compute the measure of the set of points in $L_{\epsilon}(x)$ and ${x\in E(\epsilon)}$.

However, I have some issues with this answer:

  • Shouldn't $L_{\epsilon}(x):=\{(P_{1}+\epsilon_{1}+s_{i}I_{n})x,\dotsc,(P_{m}+\epsilon_{m}+s_{i}I_{n})x\text{ linearly *dependent*}\}$ with ‘dependent’ instead of ‘independent’?
  • Since we care about vectors $\{(P_{1}+\epsilon_{1}+s_{i}I_{n})x,\dotsc,(P_{m}+\epsilon_{m}+s_{i}I_{n})x\}$ and not $\{(P_{1}+\epsilon_{1})x,\dotsc,(P_{m}+\epsilon_{m})x\}$ thus, we haven't truly decoupled both events ($L_{\epsilon}(x)$ and ${x\in E(\epsilon)}$) right? Is the proof still valid?
  • Why is it that \begin{align*} & \mathbb{P}(\{\tilde{\epsilon}:\sigma_{E(\tilde{\epsilon})}(L_{\epsilon}(x))=0\})=0 \\ & \Leftrightarrow \int_{[-\epsilon,\epsilon]^{*}}\mu(\epsilon)d\epsilon\int_{[-\epsilon,\epsilon]^{m}}\rho(s)d^{m}s\int_{E(\epsilon)}1_{L_{\epsilon}(x)}d\sigma(x)=0 \end{align*} at the end of the answer? Can you help me understand the last part of the proof? Do you think this proof is correct?
$\endgroup$
8
  • $\begingroup$ I read your original problem like this: you have a way to associate a set $E_P$ with each $m$-tuple $P=(P_1,\dots,P_m)$ of $n\times n$ positive definite matrices, and you'd like to show that the tuples $P$ for which $E_P\cap \{P_1 x,\dots, P_m x\}\neq \emptyset$ are 'unusual' or 'unstable'. Is that a reasonable summary or am I missing the point? $\endgroup$
    – DCM
    Nov 4, 2020 at 19:10
  • $\begingroup$ By 'unstable' I mean that perturbing one of the 'bad' tuples (i.e. one of the ones for which the set $E_P \cap \{P_1x, \dots, P_mx\}$ of 'bad' points in nonempty) 'usually' gives you a 'good' tuple with no bad points. $\endgroup$
    – DCM
    Nov 4, 2020 at 19:15
  • $\begingroup$ If by $\{P_1x,\dots,P_mx\}$ you mean $\{x: \{P_1x,\dots,P_mx\} \text{ linearly dependent}\}$, then yes, that is a reasonable summary. However, from the answer I got, I think that having $E_P\cap\{x: \{P_1x,\dots,P_mx\}\text{ linearly dependent}\}\neq \emptyset $ wont be possible in general (I would like to hear your thoughts). However, showing that $E_P\cap\{x: \{P_1x,\dots,P_mx\}\text{ linearly dependent}\}$ is of measure zero (in the space of $x$) almost surely is still an interesting conclusion. $\endgroup$ Nov 4, 2020 at 19:22
  • $\begingroup$ Yes - I do mean $\{ x: \{P_1x,\dots,P_mx\} \;\mbox{linearly dependent}\}$. Typo followed by copy-and-paste ;) $\endgroup$
    – DCM
    Nov 4, 2020 at 19:50
  • $\begingroup$ One other question: are your 'elipsoids' meant to be hollow (as the current definition suggests) or are they supposed to have interior? Put another way, are they 'hypersurfaces' or 'regions'? $\endgroup$
    – DCM
    Nov 6, 2020 at 19:01

1 Answer 1

0
$\begingroup$

This is not an answer, just a slightly different perspective on the original problem. If I understand your setup correctly, you have two families of hypersurfaces:

  1. those of the form $E_i(P)=\{x\in \mathbb{R}^n: x^\mathrm{T}P_ix=0\}$; and
  2. those of the form $D_i(P) = \{x\in \mathbb{R}^n: \mathrm{det}(\tilde P_i(x))= 0\}$, where $\tilde P_i(x)$ is the $i$th $m\times m$ minor of the matrix with columns $P_1x,\dots,P_mx$

parametrised by tuples $P=(P_1,\dots,P_m)$ of positive definite matrices , and want to determine whether the $P$s for which $E(P) = \bigcap_{i=1}^m E_i(P)$ meets $D(P) = \bigcap_{i=1}^m D_i(P)$ are 'unstable' in the sense that

$$ \{P\in (\mathbb{R}^{n\times n})^m:P_1,\dots, P_m \succ 0 \;\mbox{and} \;D(P)\cap E(P)\neq\emptyset\} $$

is a 'small' subset $(\mathbb{R}^{n\times n})^m$ (for some topological/measure-theoretic definition of 'small').

To me, this sounds more like a differential/algebraic geometry question than one with any essential probabilistic component.

$\endgroup$
13
  • $\begingroup$ Thanks for the comment. I agree with your posture: the probabilistic component of the problem is rather irrelevant. I get it now. Unfortunately I'm not virtuous in differential/algebraic geometry, I can read about it, but since its not my main area its very hard for me to build a full proof in this context honestly (I'm still an amateur). My hope was to find advice between the wise in this forum. So if you have any additional idea, that would help me a lot. But I will keep your comment in mind while working on this! Thanks for your time sir. $\endgroup$ Nov 8, 2020 at 15:16
  • $\begingroup$ Maybe what I'm about to say is complete nonsense, but I'll try. Using your notation, given some arbitrary $P$ one can assign a measure $\mu$ to the "surface" $E(P)$ right? (I do not mean to the measure of the whole space). Moreover, the equations for $D_i(P)$ are polynomials in $x$. Hence, points $x$ in $E(P)$ which are also in $D(P)$ must have to comply with the additional polynomials $det(\tilde{P}_i(x))$. One can use somehow the fact that the zero set of polynomials are of measure zero (?) and conclude that $\mu(E(P)\cap D(P))=0$? $\endgroup$ Nov 8, 2020 at 15:32
  • 1
    $\begingroup$ Re. "Maybe what I'm about to say is complete nonsense" - don't worry about it (and what you said wasn't nonsense). I start a lot of my sentences like that too ;) $\endgroup$
    – DCM
    Nov 8, 2020 at 17:02
  • 1
    $\begingroup$ Oh I see what you mean (i.e. you're hoping that 'most' $P$s give you overdetermined systems with no solutions). However, the fact that you have more equations than unknowns doesn't necessarily make a system overdetermined - you'd also need the equations to be suitably 'independent' (so that each equation is genuinely a new constraint). I'm can't put my finger on quite what kind of 'independence' you'd need without thinking about it a bit more, but I think it's a promising approach. $\endgroup$
    – DCM
    Nov 9, 2020 at 19:44
  • 1
    $\begingroup$ I suspect you're probably looking for a resultant type thing to tell you which $P$s give you systems which are truly overdetermined - not really my area of expertise I'm afraid but I'll still help if I can :) $\endgroup$
    – DCM
    Nov 9, 2020 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.