Skip to main content
add link, full author list
Source Link
j.c.
  • 13.6k
  • 3
  • 52
  • 90

The Gaussian surface area of the positive semidefinite cone $\mathbb{S}_d^{+} = \{ M \in \mathbb{R}^{d\times d} \colon M \succeq 0 \}$ is bounded by a constant in $[0,1]$ uniformly, according to ''Learning Geometric Concepts via Gaussian Surface Area''''Learning Geometric Concepts via Gaussian Surface Area'' by Adam R. Klivans, Ryan O'Donnell and coauthorsRocco A. Servedio.

More specifically, as shown in Definition 2 of this paper, the Gaussian surface area of any convex set $A\in \mathbb{R} ^{d\times d} $ can be written as \begin{align} \Gamma(A) = \int_{\partial A} \varphi(x) d \sigma (x),~~~~[1] \end{align} where $\varphi$ is the Gaussian measure on $\mathbb{R}^{d\times d}$ and $\sigma$ is the Euclidean surface area. By the Nazarov's inequality, for any convex set $A$ containing the origin, it holds that \begin{align} \int_{\partial A} \frac{\phi (x)}{1 + h(x) } d \sigma (x) \leq 1 - \gamma (A) \leq 1, ~~~~[2] \end{align} where $\gamma $ is the Gaussian measure and function $h$ is defined as the distance from the origin to the tangent hyperplane of $A$ which contains $h\in \partial A$. In more details, for any $h \in \partial A$, let $n_y$ be the unit normal vector to $\partial A$ at $y$. Then we define $h$ by $h(y)= \| y\|_2 \cdot \cos ( \langle y, n_y \rangle )$.

Now we go back to the PSD cone. The boundary of $\mathbb{S}_d^{+}$ is defined as \begin{align} \partial \mathbb{S}_d^{+} = \{ M\colon M \succeq 0, \textrm{rank}(M) < d\}. \end{align} For any $M \in \partial \mathbb{S}_d^{+}$, the tangent plane at $M$ is given by \begin{align} \mathcal{T}(M) = \left \{ X M + MX^{\top} \colon X \in \mathbb{R}^{d\times d} \right \}, \end{align} which implies that $M\in \mathcal{T} (M)$. Thus we have $h(M) = 0$. Combining $[1]$ and $[2]$, we conclude that the Gaussian surface area of the PSD cone is no larger than $1 - \gamma (S_d^{+})$.

The Gaussian surface area of the positive semidefinite cone $\mathbb{S}_d^{+} = \{ M \in \mathbb{R}^{d\times d} \colon M \succeq 0 \}$ is bounded by a constant in $[0,1]$ uniformly, according to ''Learning Geometric Concepts via Gaussian Surface Area'' by Adam R. Klivans and coauthors.

More specifically, as shown in Definition 2 of this paper, the Gaussian surface area of any convex set $A\in \mathbb{R} ^{d\times d} $ can be written as \begin{align} \Gamma(A) = \int_{\partial A} \varphi(x) d \sigma (x),~~~~[1] \end{align} where $\varphi$ is the Gaussian measure on $\mathbb{R}^{d\times d}$ and $\sigma$ is the Euclidean surface area. By the Nazarov's inequality, for any convex set $A$ containing the origin, it holds that \begin{align} \int_{\partial A} \frac{\phi (x)}{1 + h(x) } d \sigma (x) \leq 1 - \gamma (A) \leq 1, ~~~~[2] \end{align} where $\gamma $ is the Gaussian measure and function $h$ is defined as the distance from the origin to the tangent hyperplane of $A$ which contains $h\in \partial A$. In more details, for any $h \in \partial A$, let $n_y$ be the unit normal vector to $\partial A$ at $y$. Then we define $h$ by $h(y)= \| y\|_2 \cdot \cos ( \langle y, n_y \rangle )$.

Now we go back to the PSD cone. The boundary of $\mathbb{S}_d^{+}$ is defined as \begin{align} \partial \mathbb{S}_d^{+} = \{ M\colon M \succeq 0, \textrm{rank}(M) < d\}. \end{align} For any $M \in \partial \mathbb{S}_d^{+}$, the tangent plane at $M$ is given by \begin{align} \mathcal{T}(M) = \left \{ X M + MX^{\top} \colon X \in \mathbb{R}^{d\times d} \right \}, \end{align} which implies that $M\in \mathcal{T} (M)$. Thus we have $h(M) = 0$. Combining $[1]$ and $[2]$, we conclude that the Gaussian surface area of the PSD cone is no larger than $1 - \gamma (S_d^{+})$.

The Gaussian surface area of the positive semidefinite cone $\mathbb{S}_d^{+} = \{ M \in \mathbb{R}^{d\times d} \colon M \succeq 0 \}$ is bounded by a constant in $[0,1]$ uniformly, according to ''Learning Geometric Concepts via Gaussian Surface Area'' by Adam R. Klivans, Ryan O'Donnell and Rocco A. Servedio.

More specifically, as shown in Definition 2 of this paper, the Gaussian surface area of any convex set $A\in \mathbb{R} ^{d\times d} $ can be written as \begin{align} \Gamma(A) = \int_{\partial A} \varphi(x) d \sigma (x),~~~~[1] \end{align} where $\varphi$ is the Gaussian measure on $\mathbb{R}^{d\times d}$ and $\sigma$ is the Euclidean surface area. By Nazarov's inequality, for any convex set $A$ containing the origin, it holds that \begin{align} \int_{\partial A} \frac{\phi (x)}{1 + h(x) } d \sigma (x) \leq 1 - \gamma (A) \leq 1, ~~~~[2] \end{align} where $\gamma $ is the Gaussian measure and function $h$ is defined as the distance from the origin to the tangent hyperplane of $A$ which contains $h\in \partial A$. In more details, for any $h \in \partial A$, let $n_y$ be the unit normal vector to $\partial A$ at $y$. Then we define $h$ by $h(y)= \| y\|_2 \cdot \cos ( \langle y, n_y \rangle )$.

Now we go back to the PSD cone. The boundary of $\mathbb{S}_d^{+}$ is defined as \begin{align} \partial \mathbb{S}_d^{+} = \{ M\colon M \succeq 0, \textrm{rank}(M) < d\}. \end{align} For any $M \in \partial \mathbb{S}_d^{+}$, the tangent plane at $M$ is given by \begin{align} \mathcal{T}(M) = \left \{ X M + MX^{\top} \colon X \in \mathbb{R}^{d\times d} \right \}, \end{align} which implies that $M\in \mathcal{T} (M)$. Thus we have $h(M) = 0$. Combining $[1]$ and $[2]$, we conclude that the Gaussian surface area of the PSD cone is no larger than $1 - \gamma (S_d^{+})$.

The Gaussian surface area of the positive semidefinite cone $\mathbb{S}_d^{+} = \{ M \in \mathbb{R}^{d\times d} \colon M \succeq 0 \}$ is bounded by a constant in $[0,1]$ uniformly, according to ''Learning Geometric Concepts via Gaussian Surface Area'' by Adam R. Klivans et. aland coauthors.

More specifically, as shown in Definition 2 of this paper, the Gaussian surface area of any convex set $A\in \mathbb{R} ^{d\times d} $ can be written as \begin{align} \Gamma(A) = \int_{\partial A} \varphi(x) d \sigma (x),~~~~[1] \end{align} where $\varphi$ is the Gaussian measure on $\mathbb{R}^{d\times d}$ and $\sigma$ is the Euclidean surface area. By the Nazarov's inequality, for any convex set $A$ containing the origin, it holds that \begin{align} \int_{\partial A} \frac{1}{1 + h(x) }\cdot \phi (x) d \sigma (x) \leq 1 - \gamma (A) \leq 1, ~~~~[2] \end{align}\begin{align} \int_{\partial A} \frac{\phi (x)}{1 + h(x) } d \sigma (x) \leq 1 - \gamma (A) \leq 1, ~~~~[2] \end{align} where $\gamma $ is the Gaussian measure and function $h$ is defined as the distance from the origin to the tangent hyperplane of $A$ which contains $h\in \partial A$. In more details, for any $h \in \partial A$, let $n_y$ be the unit normal vector to $\partial A$ at $y$. Then we define $h$ by $h(y)= \| y\|_2 \cdot \cos ( \langle y, n_y \rangle )$.

Now we go back to the PSD cone. The boundary of $\mathbb{S}_d^{+}$ is defined as \begin{align} \partial \mathbb{S}_d^{+} = \{ M\colon M \succeq 0, \textrm{rank}(M) < d\}. \end{align} For any $M \in \partial \mathbb{S}_d^{+}$, the tangent plane at $M$ is given by \begin{align} \mathcal{T}(M) = \left \{ X M + MX^{\top} \colon X \in \mathbb{R}^{d\times d} \right \}, \end{align} which implies that $M\in \mathcal{T} (M)$. Thus we have $h(M) = 0$. Combining $[1]$ and $[2]$, we conclude that the Gaussian surface area of the PSD cone is no larger than $1 - \gamma (S_d^{+})$.

The Gaussian surface area of the positive semidefinite cone $\mathbb{S}_d^{+} = \{ M \in \mathbb{R}^{d\times d} \colon M \succeq 0 \}$ is bounded by a constant in $[0,1]$ uniformly, according to ''Learning Geometric Concepts via Gaussian Surface Area'' by Adam R. Klivans et. al.

More specifically, as shown in Definition 2 of this paper, the Gaussian surface area of any convex set $A\in \mathbb{R} ^{d\times d} $ can be written as \begin{align} \Gamma(A) = \int_{\partial A} \varphi(x) d \sigma (x),~~~~[1] \end{align} where $\varphi$ is the Gaussian measure on $\mathbb{R}^{d\times d}$ and $\sigma$ is the Euclidean surface area. By the Nazarov's inequality, for any convex set $A$ containing the origin, it holds that \begin{align} \int_{\partial A} \frac{1}{1 + h(x) }\cdot \phi (x) d \sigma (x) \leq 1 - \gamma (A) \leq 1, ~~~~[2] \end{align} where $\gamma $ is the Gaussian measure and function $h$ is defined as the distance from the origin to the tangent hyperplane of $A$ which contains $h\in \partial A$. In more details, for any $h \in \partial A$, let $n_y$ be the unit normal vector to $\partial A$ at $y$. Then we define $h$ by $h(y)= \| y\|_2 \cdot \cos ( \langle y, n_y \rangle )$.

Now we go back to the PSD cone. The boundary of $\mathbb{S}_d^{+}$ is defined as \begin{align} \partial \mathbb{S}_d^{+} = \{ M\colon M \succeq 0, \textrm{rank}(M) < d\}. \end{align} For any $M \in \partial \mathbb{S}_d^{+}$, the tangent plane at $M$ is given by \begin{align} \mathcal{T}(M) = \left \{ X M + MX^{\top} \colon X \in \mathbb{R}^{d\times d} \right \}, \end{align} which implies that $M\in \mathcal{T} (M)$. Thus we have $h(M) = 0$. Combining $[1]$ and $[2]$, conclude that the Gaussian surface area of the PSD cone is no larger than $1 - \gamma (S_d^{+})$.

The Gaussian surface area of the positive semidefinite cone $\mathbb{S}_d^{+} = \{ M \in \mathbb{R}^{d\times d} \colon M \succeq 0 \}$ is bounded by a constant in $[0,1]$ uniformly, according to ''Learning Geometric Concepts via Gaussian Surface Area'' by Adam R. Klivans and coauthors.

More specifically, as shown in Definition 2 of this paper, the Gaussian surface area of any convex set $A\in \mathbb{R} ^{d\times d} $ can be written as \begin{align} \Gamma(A) = \int_{\partial A} \varphi(x) d \sigma (x),~~~~[1] \end{align} where $\varphi$ is the Gaussian measure on $\mathbb{R}^{d\times d}$ and $\sigma$ is the Euclidean surface area. By the Nazarov's inequality, for any convex set $A$ containing the origin, it holds that \begin{align} \int_{\partial A} \frac{\phi (x)}{1 + h(x) } d \sigma (x) \leq 1 - \gamma (A) \leq 1, ~~~~[2] \end{align} where $\gamma $ is the Gaussian measure and function $h$ is defined as the distance from the origin to the tangent hyperplane of $A$ which contains $h\in \partial A$. In more details, for any $h \in \partial A$, let $n_y$ be the unit normal vector to $\partial A$ at $y$. Then we define $h$ by $h(y)= \| y\|_2 \cdot \cos ( \langle y, n_y \rangle )$.

Now we go back to the PSD cone. The boundary of $\mathbb{S}_d^{+}$ is defined as \begin{align} \partial \mathbb{S}_d^{+} = \{ M\colon M \succeq 0, \textrm{rank}(M) < d\}. \end{align} For any $M \in \partial \mathbb{S}_d^{+}$, the tangent plane at $M$ is given by \begin{align} \mathcal{T}(M) = \left \{ X M + MX^{\top} \colon X \in \mathbb{R}^{d\times d} \right \}, \end{align} which implies that $M\in \mathcal{T} (M)$. Thus we have $h(M) = 0$. Combining $[1]$ and $[2]$, we conclude that the Gaussian surface area of the PSD cone is no larger than $1 - \gamma (S_d^{+})$.

Source Link
Steve
  • 1.1k
  • 6
  • 18

The Gaussian surface area of the positive semidefinite cone $\mathbb{S}_d^{+} = \{ M \in \mathbb{R}^{d\times d} \colon M \succeq 0 \}$ is bounded by a constant in $[0,1]$ uniformly, according to ''Learning Geometric Concepts via Gaussian Surface Area'' by Adam R. Klivans et. al.

More specifically, as shown in Definition 2 of this paper, the Gaussian surface area of any convex set $A\in \mathbb{R} ^{d\times d} $ can be written as \begin{align} \Gamma(A) = \int_{\partial A} \varphi(x) d \sigma (x),~~~~[1] \end{align} where $\varphi$ is the Gaussian measure on $\mathbb{R}^{d\times d}$ and $\sigma$ is the Euclidean surface area. By the Nazarov's inequality, for any convex set $A$ containing the origin, it holds that \begin{align} \int_{\partial A} \frac{1}{1 + h(x) }\cdot \phi (x) d \sigma (x) \leq 1 - \gamma (A) \leq 1, ~~~~[2] \end{align} where $\gamma $ is the Gaussian measure and function $h$ is defined as the distance from the origin to the tangent hyperplane of $A$ which contains $h\in \partial A$. In more details, for any $h \in \partial A$, let $n_y$ be the unit normal vector to $\partial A$ at $y$. Then we define $h$ by $h(y)= \| y\|_2 \cdot \cos ( \langle y, n_y \rangle )$.

Now we go back to the PSD cone. The boundary of $\mathbb{S}_d^{+}$ is defined as \begin{align} \partial \mathbb{S}_d^{+} = \{ M\colon M \succeq 0, \textrm{rank}(M) < d\}. \end{align} For any $M \in \partial \mathbb{S}_d^{+}$, the tangent plane at $M$ is given by \begin{align} \mathcal{T}(M) = \left \{ X M + MX^{\top} \colon X \in \mathbb{R}^{d\times d} \right \}, \end{align} which implies that $M\in \mathcal{T} (M)$. Thus we have $h(M) = 0$. Combining $[1]$ and $[2]$, conclude that the Gaussian surface area of the PSD cone is no larger than $1 - \gamma (S_d^{+})$.