All Questions
1,544 questions
1
vote
0
answers
49
views
Comparing convex planar regions of equal perimeter and area - 2
We try to extend On comparing planar convex regions of equal perimeter and area .
Given two planar convex regions C1 and C2 both with unit perimeter, we define the difference between C1 and C2 as the ...
- 5,979
5
votes
1
answer
258
views
Dimension reduction for non-negativity of elementary symmetric polynomials
Fix integers $1 \leq k \leq n$ and suppose $\mathbf{x} \in \mathbb{R}^n$ is such that $e_j(x_1,x_2,\ldots,x_n) \geq 0$ for all $1 \leq j \leq k$, where $e_j$ is the $j$-th elementary symmetric ...
- 6,351
0
votes
1
answer
101
views
Estimation via projecting onto a convex body
Assume that $\theta$ is in a convex body $K \in \mathbb{R}^n$ and we observe $y = \theta + z$, where $z$ is a noise term (following, say, the normal distribution). Consider an estimator of $\theta$ by ...
- 773
1
vote
1
answer
90
views
Affine semigroup generating a lattice
This is a cross-post from MSE.
Everything is assumed to be finite-dimensional. Let $S$ be a finitely generated affine semigroup (i.e. a subsemigroup of a lattice $N$ of a Euclidean space). Assume that ...
- 1,374
0
votes
0
answers
118
views
Weak derivative of projection onto probabilist's simplex
Let $\Delta_n:=\{x\in [0,1]^n:\boldsymbol{1}^{\top}x=1\}$ denote the probabilist's $n$-simplex and let $P:\mathbb{R}^n\rightarrow\Delta_n$ denote the (Euclidean) metric projection onto this simplex ...
- 5,405
2
votes
1
answer
165
views
Existence of preferred direction for a random vector with arbitrary distribution on sphere, under a condition on its covariance matrix
Let $X$ be random vector on the unit-sphere $S_{n-1}$ in $\mathbb R^n$. We don't assume that the distribution of $X$ is uniform on $S_{n-1}$
I'm interested in proving the existence of a (...
- 6,853
1
vote
0
answers
98
views
Solution of a simple optimization problem
Let $\mathbf{U}_1$ and $\mathbf{U}_2$ be two arbitrary unitary matrices and $\mathbf{D}$ be a diagonal matrix. What is the solution of the following optimization problem?
\begin{align}
\min_{\mathbf{...
- 287
0
votes
0
answers
124
views
The best unitary matrices that approximate a matrix product
Let $\mathbf{A}$ be an arbitrary $N\times N$ complex matrix. Moreover, $\mathcal{U}_1$ and $\mathcal{U}_2$ are distinct subsets of all unitary matrices. Suppose the matrices $\mathbf{U}_1$ and $\...
- 287
2
votes
2
answers
104
views
Monotonicity of perimeter of convex subsets of hyperbolic plane
I think that the perimeter of convex compact sets on the hyperbolic plane is monotone with respect to inclusion.
I am looking for a reference to the above fact.
- 21.8k
1
vote
0
answers
76
views
Convex planar regions with optimal average 'centralness' and 'depth'
For a planar convex region $C$ and an interior point $P$ we define:
the centralness ratio at $P$ is
$$\min\left(\frac{\text{shorter portion of }\chi}{\text{longer portion of }\chi}:\chi\text{ is a ...
- 5,979
1
vote
0
answers
35
views
How to chose the start vector for the MTZ variables
In the context of LP-formulations for the Traveling Salesman Problem the MTZ constraints prevent subtours via $n$ (i.e. effectively $n-1$) additional variables $$u_1=1\\2\le u_2,\,\dots ,\,u_n\le n\\ ...
- 13.2k
1
vote
1
answer
197
views
Sufficient conditions for the boundary unit-normal vector field of a closed convex set to be Lipschitz continuous
This is followup to the following question: On the Lipschitz continuity of the unit-normal vector field of a polytope
Let $C$ be a (nonempty) closed convex subset of $\mathbb R^n$. Note that to every ...
- 6,853
2
votes
1
answer
304
views
On the Lipschitz continuity of $x \mapsto \arg\min_{c \in C}d(x,c)$ w.r.t Hausdorff distance
Let $C$ be a (nonempty) compact subset of euclidean $\mathbb R^n$, and consider the set-valued map $p_C:\mathbb R^n \to 2^C$ defined by
$$
p_C(x) = \{c \in C \mid \|x-c\| = \mbox{dist}(x,C)\},
$$
...
- 6,853
1
vote
1
answer
139
views
On the Lipschitz continuity of the unit-normal vector field of a polytope
Let $\mu$ be a probability measure on $\mathbb R^n$ and let $P$ be a compact polytope in $\mathbb R^n$. For any $x \in \mathbb R^n \setminus P$, let $p(x) \in P$ be (unique!) point in $P$ which is ...
- 6,853
2
votes
1
answer
113
views
Existence of fine approximate of a convex body in $\mathbb R^d$ with convex hull of $\mathcal O(d)$ points
Let $K$ be a convex body in $\mathbb R^d$ which contains the origin and let $\theta \in (0,1)$.
Question. Is it always possible to find $n$ points $x_1,\dotsc,x_n \in \mathbb R^d$ such that
$$
\theta ...
- 6,853
2
votes
1
answer
137
views
Optimal number of half-spaces in the $H$-representation of the convex hull of $n$ points in $\mathbb R^d$
Let $P$ be the polytope obtained as the convex hull of $n$ points in $\mathbb R^d$. This is the $V$-representation of $P$. Note that $P$ can also be represented as an intersection of closed half-...
- 6,853
7
votes
4
answers
476
views
What does $\mathbb E_V \max_{x \in V,\,\|x\|=1} x^T Ax$ evaluate to when $V$ is random $k$-dim suspace of $\mathbb R^n$ and $A$ is fixed psd matrix?
Let $G_{k,n}$ be the grassmannian of $k$-dimensional vector spaces of $\mathbb R^n$. By the Courant–Fisher characterization, the $k$th largest eigenvalue of an $n \times n$ psd matrix $A$ is given by
$...
- 6,853
1
vote
0
answers
111
views
On finding optimal convex planar shapes to cover a given convex planar shape
Covering a specific convex shape S with n copies of another specified convex shape S' (which may be different from S) is well studied - for example, https://erich-friedman.github.io/packing/index.html....
- 5,979
1
vote
0
answers
153
views
Is there a polynomial expression for the volume of the following set?
Denote the unit $\ell_2$ ball in $\mathbb{R}^n$ as $\mathcal{B}_n$. It is widely kown that for a convex body $\mathcal{K}\subseteq \mathbb{R}^n$, the $n$-dimensional volume of the parallel body $\...
- 550
9
votes
2
answers
379
views
Which convex bodies roll straight?
Let $K$ be a convex body in $\mathbb{R}^3$.
Suppose $K$ is held at some position and orientation on an inclined plane,
and released.
Let there be sufficient friction so that it rolls without slippage.
...
- 151k
3
votes
1
answer
193
views
Well-behaved trajectories
Call trajectory any continuous function $f: \mathbb{R}_{\geq 0} \to \mathbb{R}^n$ (here, $\mathbb{R}_{\geq 0}$ is interpreted as time).
A polyhedral partition of $\mathbb{R}^n$ is a finite set of ...
- 141
7
votes
2
answers
635
views
RELU representation of $\max(x,y,z)$
Here is a question that occurred to me while learning about neural networks. For $t\in\mathbb{R}$ put $t_+=\max(0,t)$, so $t_+=t$ if $t\geq 0$ and $t_+=0$ if $t\leq 0$. (This is RELU=rectified linear ...
- 56.9k
1
vote
1
answer
92
views
How to compute external angles of a hypersimplex?
Recently, I concern with the volume of the outer parallel body of a hypersimplex that is defined as follows
$$
\mathcal{H}_s(n,k)=\left\{ (x_1,\cdots,x_n):\sum_{i=1}^n x_i=k,x_i\in[0,1] \right\},
$$
...
- 550
1
vote
0
answers
200
views
Drawing a 3D object in a 3D environment, and converting to math [closed]
So I have been granted a free time and I want to work on a project but first I had to research.
As we know, lines have infinite points, and with lines, we can create infinite shapes. I want to let ...
- 11
0
votes
0
answers
108
views
How to find a set given its support function
Let $\mathcal{U}$ be a convex and compact set. Its support function is defined as $\delta^*(v|\mathcal{U})=\sup_{u\in \mathcal{U}} v^T u$. Assume that we are given the support function $\delta^*(v|\...
- 53
3
votes
0
answers
201
views
Hausdorff measure of the unit ball of a norm on $\mathbb{R}^n$ is a universal constant
In [1], Kirchheim proved the area formula for Lipschitz maps $f\colon \mathbb{R}^n\to X$ where $X$ is an arbitrary metric space, using the notion of metric differentiability. The metric derivative of $...
- 622
0
votes
0
answers
40
views
Subtour-gluing constraints for ILP formulation of TSPs
If one doesn't want to introduce additional variables to the ILP of a TSP instance, one has to add exponentially many so-called subtour-elimination constraints; in practical calculations subtour-...
- 13.2k
4
votes
0
answers
54
views
On ways to measure the difference between two planar convex regions
This earlier post attempted to quantify the difference between a pair of planar convex regions of equal area and perimeter using Hausdorff distance:
On comparing planar convex regions of equal ...
- 5,979
1
vote
1
answer
67
views
Lower-bound for $\mathbb E[e^{-b(v^\top X - c)^2}]$, when $X$ is log-concave in high-dimensions
Let $d$ be a large positive integer. Fix a unit-vector $v \in \mathbb R^d$, and scalars $b,c \in \mathbb R$ with $b > 0$. Let $X$ be a log-concave random vector in $\mathbb R^d$ normalized so that ...
- 6,853
6
votes
1
answer
148
views
Isometric imbedding of a 2-disk into Euclidean 3-space
Let us call a cap the intersection of the boundary of 3-dimensional convex compact set $K$ in $\mathbb{R}^3$ with a half-space bounded by a plane $H$ such that the orthogonal projection to $H$ of this ...
- 21.8k
3
votes
1
answer
118
views
Is a cap an Alexandrov space?
Let us call a cap the intersection of the boundary of 3-dimensional convex compact set $K$ in $\mathbb{R}^3$ with a half-space bounded by a plane $H$ such that the orthogonal projection to $H$ of this ...
- 21.8k
6
votes
3
answers
447
views
Isoperimetric inequality for $\epsilon$-expansion of a set only along a certain subspace
Let $\gamma_n$ be the standard gaussian distribution on $\mathbb R^n$. Let $V$ be a $k$-dimensional subspace of $\mathbb R^n$. Finally let $A$ be any (nonempty) Borel subset of $A$ with $\gamma_n(A) = ...
- 6,853
3
votes
1
answer
143
views
Finding the smallest centrally symmetric region that contains a convex planar region
Given a convex polygonal region C, how does one find/characterize the smallest zonogon (centrally symmetric convex polygon https://en.wikipedia.org/wiki/Zonogon) that contains C?
Note 1: In question ...
- 5,979
1
vote
0
answers
65
views
Minimum bounding rectangle of symmetric convex bodies in the plane : is the ball the worst case
The minimal rectangle containing the euclidean ball in the plane is the standard cube $B_\infty = [-1;1]^2$. I would like to know if the euclidean ball is the worst symmetric convex body to be ...
- 245
4
votes
1
answer
110
views
Separation of convexity on uniquely geodesic space
A metric $d: X \times X \to [0,\infty)$
is said to be intrinsic provided that the distance between any two points is the infimum of the lengths of
paths joining the points. A space is an inner metric ...
- 2,083
1
vote
0
answers
72
views
A ratio to measure 'roundedness' of planar convex regions
Ref: A center of convex planar regions based on chords
The above discussion quotes the definition of 'centralness coefficient' and defines a center of a planar convex region. 1/2 is the least possible ...
- 5,979
4
votes
1
answer
193
views
How to solve this minimax matrix optimization problem?
Recently, I want to know how well can a $\ell_1$ ball be approximated by the image of a $\ell_2$ ball under a linear transform. I formulate this problem as the following optimization problem.
\begin{...
- 550
5
votes
0
answers
233
views
Reference request for convex geometry?
I am looking for a reference for an elementary convex geometry.
In Appendix A (page 1810) of this paper by Green and Tao, they cover some basic results from elementary convex geometry. The results ...
- 3,625
2
votes
0
answers
71
views
On cutting convex regions with average values of quantities minimized
This post continues from Cutting convex regions into equal diameter and equal least width pieces - 2 and Cutting convex regions into equal diameter and equal least width pieces - 3
A basic (and to my ...
- 5,979
0
votes
0
answers
96
views
Why is Gaussian distribution always chosen for smoothed analysis?
I came across the algorithmic perfomance analysis model of smoothed analysis. In all references that I read a Gaussian distribution was used for perturbation (e.g. Spielman and Teng 2004 for the ...
- 29
1
vote
1
answer
82
views
Do we really need degree constraints for ILP formulations of TSP problems
The Dantzig-Fulkerson ILP-formulation of the symmetric TSP is
$$\min\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^n c_{ij}x_{\lbrace i,j\rbrace}\quad\text{s.t.}\\ \sum\limits_{j\ne i,\,j=1}^n x_{\lbrace ...
- 13.2k
1
vote
0
answers
52
views
When the summands of a positive definite matrix are positive definite
Let $A,B$ be two real symmetric matrices. Let $C = A+B$ be a positive-definite matrix. Write $C>0$ for $C$ being positive-definite. Suppose that $A>0 \implies C>0$ and $B > 0 \implies C>...
- 71
4
votes
0
answers
603
views
Mixed volumes of Newton–Okounkov bodies
Let $X$ be a smooth irreducible projective complex variety of dimension $n$. Let $X=Y_0\supseteq\cdots\supseteq Y_n$ be an admissible flag. Consider $n$ line bundles $L_1,\ldots,L_n$ on $X$. Let $\...
- 329
3
votes
1
answer
173
views
Parameterizing the space of convex quadrilaterals
If $P=\mathbb{R}^2$ is the plane, is there a continuous surjection from $P^4$ to the space of convex quadrilaterals?
Specifically, I'm looking for a continuous $f:P^4\to P^4$ such that:
[convexity] ...
user44143
1
vote
0
answers
60
views
Proving convexity of total distance between two parties with one meeting point [closed]
Apologies if I´m not using the correct mathematical wording or notation. I´ll try my best in the following problem
Suppose you have a coordinate system and 5 coordinates ($A1$, $A2$, $B1$, $B2$, $M_{x,...
- 11
3
votes
1
answer
323
views
Inscribed $n$-gons of maximum perimeter for an ellipse
It appears that the max area inscribed $n$-gon for an ellipse is not unique - if one inscribes a regular $n$-gon in a circle with radius a (there are infinitely many orientations for this inscribed ...
- 5,979
0
votes
1
answer
175
views
Maximum vertex amount of low-dimensional simplex projection
Consider an arbitrary simplex $\mathcal{S} \subseteq \mathbb{R}^n$ ($\mathcal{S}$ is a polytope in $\mathbb{R}^n$ with $n+1$ vertices and non-empty interior). Let ${\bf P} \in \mathbb{R}^{m \times n}, ...
- 235
1
vote
0
answers
65
views
To extend the Steiner-Lehmus theorem
The Steiner Lehmus theorem (https://en.wikipedia.org/wiki/Steiner%E2%80%93Lehmus_theorem) states: Every triangle with two angle bisectors of equal lengths is isosceles.
Question: What could one say ...
- 5,979
6
votes
0
answers
192
views
Does the ball maximize the "kissing probability" of symmetric convex bodies? [duplicate]
Given a symmetric convex body $K \subset \mathbb{R}^n$ (i.e., a bounded symmetric convex set with non-empty interior), I am interested in the following quantity
$$p_K := \Pr_{x_1, x_2 \sim K}[x_1 \in ...
- 1,016
1
vote
0
answers
58
views
Second-order envelope theorem for linear programming
Consider parameterized linear programming $V(\theta) = \max_x \langle c(\theta),x\rangle$ s.t. $A(\theta)x\leq b(\theta)$, $x\geq 0$. Let's also assume $c,A,b$ are infinitely differentiable with ...
- 373