An inequality from the “Interlacing-1” paper

This question is in reference to this paper, http://annals.math.princeton.edu/wp-content/uploads/annals-v182-n1-p07-p.pdf (or its arxiv version, http://arxiv.org/abs/1304.4132) For the argument to work one seems to need that for the symmetric ±1 signing adjacency matrix of the graph, As, it holds that, max−root(∑s∈{0,1}mdet(xI−As))≤max−root(Es∈{0,1}m[det(xI−As)]) But why should this inequality be true? and the argument works because the polynomial on the … Read more

Basin of Attraction

I have a function F which is defined as follows: F(x)=N∑i=1f(zTix) where zi are known m×1 vectors, x is an m×1 vector, and for t∈R, f(t)=11+e−t/σ with a known σ (a sigmoid function). For a local or global maximum of F(x), I would like to characterize the basin of attraction—the set of all starting points … Read more

Designing Character Other Than Temperature for Simulated Annealing on Combinatorial Optimization

Many research on designing temperature for simulated annealing is carried out. We wonder if there is any research on designing general feature of the Hamiltonian used in Simulated Annealing. For example, consider the Ising optimization problem on a very large graph: at each time, a random vertex v is choosen; one updates the state of … Read more

Covering Number of a Positive Semidefinite Cone (Approximate the Objective of a SDP)

I was wondering what the covering number of a positive semidefinite cone is. Consider the semidefinite optimization program \begin{align} \max\langle \mathbf{C}, \mathbf{X} \rangle~~\text{subject to}~~ \langle \mathbf{A}_i, \mathbf{X} \rangle \leq b_i, i= 1,\ldots, m, \mathbf{X} \succeq \mathbf{0}. \end{align} Is it possible to find finite number of elements $\{ \mathbf{V}_k \}_{k=1}^N$ in the SDP cone \begin{align} \left\{ … Read more

How well does an estimator perform on another dataset?

Suppose X∼N(0,Σ) is a d-dimensional Gaussian random vector. And we have 2n i.i.d sample X1,…,Xn,…,X2n. Let ˆΣ1=1n∑ni=1XiX⊤i and ˆΣ2=1n∑2ni=n+1XiX⊤i be the sample covariance matrix of the first half and second half data. For the first one, I use it to solve the following optimization problem: for i=1:d, min where e_i is the i-th basis in … Read more

Stochastic subgradient descent almost sure convergence

I was reading up on stochastic subgradient descent, and most sources i could find via google search give quick proofs on convergence in expectation and probability, and say that proofs of almost sure convergence exist. Can anyone point me to a proof of this claim? I would be especially interested in proving the following claim … Read more

Derivative of rank rr approximation of matrix

Let Y∈Rn×c and r be an integer with 1≤r≤rank(Y). Consider the problem minimize‖ which seeks a n-by-c matrix of rank r which is closest to Y w.r.t the Frobenius norm. The Eckart–Young–Mirsky theorem shows that the choice X = \hat{Y}(r) := Y\Pi(r) solves this problem, where \Pi(r) := V(r)V(r)^T the projection onto the subspace spanned … Read more

Best Approximation in Operator/non-Frobenius Norm

Since the Frobenius norm on matrices is generated by an inner product, solving the optimization/approximation problem of approximating an operator X with a scalar multiple of another operator Y minimize:‖ has a closed form solution \alpha = \frac{\langle X, Y \rangle}{\langle Y,Y \rangle} via an orthogonal projection. What if I want to consider a non-Frobenius … Read more

Using Linear Programming as an iterative procedure

Suppose, we have a linear program and an optimal solution to it. Suppose now, we get a new constraint. We want to obtain an optimal solution to the given linear program extended by that new constraint. Is it possible to use the calculated optimal solution to do it in some clever way? Obviously, if the … Read more

Minimization over a convex function of equal vs unequal success probabilities of Bernoulli random variables

Let $U_1,U_2,\ldots,U_n$ be $n\geq 2$ mutually independent Bernoulli random variables. There are two cases of interest: $1.$ The random variables $U_1,U_2,\ldots,U_n$ are identically distributed; $U_1\sim \operatorname{Bernoulli}(p)$ with probability $1/2$. Let $P_0$ be the associated probability measure, i.e. $$P_0(U_1,\ldots,U_n)=P(U_1,\ldots,U_n\mid U_1\sim \operatorname{Bernoulli}(p))$$ $U_1\sim \operatorname{Bernoulli}(1-q)$ with probability $1/2$. Let $P_1$ be the associated probability measure, i.e. $$P_1(U_1,\ldots,U_n)=P(U_1,\ldots,U_n\mid U_1\sim … Read more