Skip to main content

All Questions

53 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
7 votes
0 answers
1k views

Closed-form solution of a linear programming question

Among all the probability matrices \begin{equation*} P = \left(\begin{array}{cccc} p_{00} & p_{01} & \ldots & p_{0,J-1} \\ p_{10} & p_{11} & \ldots & p_{1,J-1} \\ \vdots & \...
Jerry Jiannan Lu's user avatar
7 votes
0 answers
217 views

Characterizing matrices with rank constraint

Given matrix $M\in\Bbb\{0,1\}^{n\times n}$, is there a nice method to characterize $$\mathscr{D}[M]=\{Q\in\Bbb\{0,1\}^{n\times n}:\mathsf{rank}(M-Q)= \mathsf{rank}(Q),\quad M-Q\in\Bbb\{0,1\}^{n\times ...
Turbo's user avatar
  • 13.9k
7 votes
0 answers
209 views

Numerical linear algebra: how to compute $B^TC^{−1}B$ efficiently

Hi, my question is similar to this one. I have to compute $B^TC^{−1}B$, where $C$ is a strictly positive definite $n\times n$ matrix and $B$ is $n\times m$. The matrix $C$ is huge ($n$ up to a ...
Manuel Schmidt's user avatar
6 votes
0 answers
136 views

Minimizing $\det(D)$ for all diagonal matrices $D$ that satisfy $D+B \succeq 0$

Let $A$ be an $n \times n$ real matrix and let $B$ be the block bipartite matrix $$B = \begin{bmatrix} 0&A \\ A^{T}&0 \end{bmatrix}$$ I came across the following optimization problem, which ...
user135520's user avatar
5 votes
0 answers
330 views

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$ $$\...
Conner DiPaolo's user avatar
4 votes
0 answers
307 views

Derivative of rank $r$ approximation of matrix

Let $Y \in \mathbb R^{n \times c}$ and $r$ be an integer with $1 \le r \le \operatorname{rank}(Y)$. Consider the problem $$\text{minimize} \|Y-X\|_{\text{Fro}}^2\text{ over }X \in \mathbb R^{n \times ...
dohmatob's user avatar
  • 6,853
4 votes
0 answers
206 views

Basin of Attraction

I have a function $F$ which is defined as follows: $$ F(x) = \sum_{i=1}^N f(z_i^T x) $$ where ${z_i}$ are known $m \times 1$ vectors, $x$ is an $m \times 1$ vector, and for $t\in \mathbb{R}$, $f(t) = \...
Mkl's user avatar
  • 291
4 votes
0 answers
126 views

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 ...
InterlacingStudent's user avatar
3 votes
0 answers
122 views

Convex optimization upper bound for a non-linear optimization

Is there any good convex optimization problem based upper-bound for the following non-linear optimization problem? \begin{align} \max_{x_1,\ldots,x_N}&\quad \sum_{n=1}^{N} \log(1+\frac{x_n}{1+\...
Math_Y's user avatar
  • 287
3 votes
0 answers
116 views

convex approximation for a non convex function

Consider the function $f\left( {{x_1},...,{x_M},{y_1},...,{y_N}} \right) = \left( {\sum\limits_{j = 1}^M {{\alpha _j}{x_j}} } \right)\left( {{e^{ - \sum\limits_{i = 1}^N {{\beta _i}{y_i}} }}} \right)$...
user51780's user avatar
  • 275
2 votes
0 answers
119 views

Seeking insights on bounded set positive solutions for a set of linear systems in $\mathbb{R}^n$

Before delving into my query, I'd like to provide some context. Consider a continuous function $f:\mathbb{R}^{k}\rightarrow\mathbb{R}^{m}$ and a compact set $\mathcal{B}\subset \mathbb{R}^{k}$ (...
Diego Fonseca's user avatar
2 votes
0 answers
178 views

Can we get the exact solution of large-scale quadratic programming problems (quadratic objective, linear inequality constraints) using KKT condition?

Crossposted at Computational Science SE Consider a quadratic programming problem with the following format: $$ \text{min} Q(x) = c^Tx+\frac{1}{2}x^TDx \\ $$ $$ \text{s.t.} Ax\leq b, \\ x\geq 0 $$ ...
ximeng fan's user avatar
2 votes
1 answer
506 views

Effect of duplicated row on singular values and vectors

Let $\mathbf{A}$ be a $n\times n$ matrix with Singular Value Decomposition (SVD) $\mathbf{A}=\mathbf{U}\mathbf{S}\mathbf{V}$ and $\mathbf{a}_1$ be the first row of $\mathbf{A}$. What can we say about ...
Math_Y's user avatar
  • 287
2 votes
0 answers
618 views

block diagonal approximation of (SPD) matrix

I am interested in approximating a symmetric matrix in a block diagonal form, i.e. compute just some entries of the matrix located in blocks around the diagonal. Are there any theoretical guarantees ...
Foivos's user avatar
  • 335
2 votes
0 answers
46 views

Notion of distance between linear programs

Consider the linear programming problem \begin{align} \max_{x}&~c^Tx \\~s.t.~~a^Tx &\leq B~,~0\leq x_i \le1 \end{align} where $c$ and $a$ are $n \times 1$ given non-negative vectors. $B$ is a ...
dineshdileep's user avatar
  • 1,421
2 votes
0 answers
298 views

Is the following map a diffeomorphism?

Context: I'm working on a convergence theorem for an accelerated version of an iterative optimisation algorithm. At regularly-spaced intervals during the algorithm, a number of previous (...
Matt Geleta's user avatar
2 votes
0 answers
210 views

projection of a matrix to the the space such that the diagonal elements are the greatest

Suppose there is a symmetric matrix $A$ in $\mathcal{S}^n$. I would like to compute the nearest symmetric matrix $X \in \mathcal{S}^n$ such that $X_{ij} \le X_{ii}$, $i ,j \in \{1,...,n \}$. In other ...
Pew's user avatar
  • 263
2 votes
0 answers
156 views

Optimization of quadratic form with band matrices

Let $A_1$ be the $N \times N$-matrix for which $a_{i,j} = 1$ for $i=j$ and 0 otherwise. Let $A_2$ be the matrix for which $a_{i,j}=1$ for $|i-j| \leq 1$ and 0 otherwise. Similarly define $A_3$ (which ...
Kurisuto Asutora's user avatar
2 votes
0 answers
299 views

Practical application of envelope theorem for linear programs

Assume that we have solved a (standard) linear program $$ \text{minimize}_{x\in {\mathbb R^n}}\,\, c_0^Tx, \,\,\,\,\, \text{s.t. } A_0x \leq b_0, $$ and would like to know how sensitive is the optimal ...
Bogdan Grechuk's user avatar
2 votes
0 answers
199 views

Constrained absolute orientation of 3D point sets

Let us assume we have two 3D point sets, $P=\{p_i\}$ and $Q=\{q_i\}$, and that we need to recover the transformation that takes $P$ as close to $Q$ as possible. In particular, I am interested in roto-...
AugSB's user avatar
  • 121
2 votes
0 answers
210 views

Finding optimal linear transformation for intersection of convex polytopes

I previously posted this on MathSE and am now trying here. I have the following situation, as shown in the following diagram: $W=\{w_i\}_{i=1..|W|}$ is a set of vertices (show in diagram in blue) ...
Artemy's user avatar
  • 695
1 vote
0 answers
37 views

When does an optimal input sequence for a discrete-time system exist?

Suppose an LTI discrete-time system is given by the equations $$ x_{k+1} = Ax_k + Bu_k,\\ y_{k} = Cx_k + Du_k $$ with $x_k\in\mathbb{R}^{m}$, $y_k\in\mathbb{R}^{n}$ and $u_k\in\mathbb{R}^{p}$ and $\...
Benjamin Tennyson's user avatar
1 vote
0 answers
73 views

What is the closed form of a polyhedral cone's dual cone?

A polyhedral cone can be defined as $$ \mathcal{K} = \{x~|~Ax\preceq 0\}, $$ where $A \in \mathbb{R}^{m \times n}$, $x\in \mathbb{R}^n$ and $\preceq$ denotes component-wise less than and equal to. The ...
zhamao dra's user avatar
1 vote
0 answers
204 views

Matrix relative condition number

I've been working on some distributed optimization problems and faced a bit of a challenge with the following question. Given $A_1, A_2, .., A_m \in M_n({\mathbb{R})} $ symmetric positive definite ...
TrevLou's user avatar
  • 11
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{...
Math_Y's user avatar
  • 287
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>...
Kaleb's user avatar
  • 71
1 vote
0 answers
176 views

Maximum mutual information of random unitary transformation

Let $\mathbf{U}$ and $\mathbf{V}$ be random unitary matrices independent of random input vector $\mathbf{x}$. Moreover, $\mathbf{z}$ be random iid complex Gaussian vector with zero mean and identity ...
Math_Y's user avatar
  • 287
1 vote
0 answers
139 views

Subgradient chain rule

Suppose $$F:\mathbb{R}^n \to \mathbb{R},\; F(x)=\mathrm{max}_\mathrm{eig}(C-\mbox{diag}(x)).$$ I am trying to find a subgradient of $F$ at $x_0$. A subgradient of $\mathrm{max}_\mathrm{eig}$ is given ...
Stephen T.'s user avatar
1 vote
0 answers
150 views

Minimax optimization of diagonal entries of function of matrix

Let $\mathbf{A}$ and $\mathbf{U}$ be arbitrary complex $M\times N$ and $N\times M$ matrices, respectively. Let denote superscript $(\cdot)^{\dagger}$ and $(\cdot)^{\mathrm{H}}$ as pseudo-inverse and ...
Math_Y's user avatar
  • 287
1 vote
0 answers
208 views

Maximum theorem with linear constraints. On parametric continuity of in optimization

Given \begin{align} s(\theta)= &\text{arg min}( g( \boldsymbol{x}) ) \\ \text{subject to }& \boldsymbol{A}(\theta) \boldsymbol{x} = \boldsymbol{b}(\theta) \\ &c_1 \le x_i \le c_2 , ...
Einar U's user avatar
  • 88
1 vote
0 answers
163 views

Properties of vector combinations in the non-negative orthant

Given a vector $x \in \mathbb{R}^{n}_{0+}$ such that $x = \sum^{k}_{i=1} \alpha_{i}v_{i}$, the vectors $(v_{1},...,v_{k}) \in \mathbb{R}^{n}_{0+}$ are an independent set, $k < n$, and $\alpha_{i} &...
nick.schachter's user avatar
1 vote
0 answers
138 views

Matrix completion in $2\times2$ case by nuclear norm minimization to guarantee rank $1$?

Does fixing diagonal entries and minimizing nuclear norm under weighted sum of entries conditions produce a rank $1$ matrix? I think the answer for this is no. At least could it be true in $2\times2$ ...
Turbo's user avatar
  • 13.9k
1 vote
0 answers
483 views

minimize norm of matrix product

I have the matrix Product $PAP^H$ and I need to minimize $\|(PAP^H)^{-1}\|^2$ (over $P$ and Frobenius norm). $A$ is a positive definite Hermitian matrix and $P$ has the structure $$P=\left[\begin{...
F Researcher's user avatar
1 vote
0 answers
481 views

psd condition for matrix completion

The nuclear norm minimization for the matrix completion problem is given by \begin{align} \textrm{minimize } \quad &\|X\|_{*}\\ \textrm{subject to } \quad & X_{ij}=M_{ij} \quad \forall (i,j)...
felasfaw's user avatar
  • 221
1 vote
0 answers
1k views

Analytic formula for minimizing the maximum inner product of a set of vectors

Given $x_j\in\mathbb{R}^n$, $j=1,\ldots,p$, find $$ \widehat{w} \in \arg\min_{\Vert w\Vert=1}\max_{1\le j\le p} |\langle w,x_j\rangle|. $$ I am also interested in the special case where we further ...
JohnA's user avatar
  • 710
1 vote
0 answers
227 views

Find optimal value for a regularization parameter in generalized eigenvalue problem

Consider the generalized eigenvalue problem : $ \Sigma_{XY} \Sigma_{YX} {W} = \lambda \Sigma_{XX} {W} $ where $\Sigma_{XX} $ and $\Sigma_{XY}$ are sample covariance matrices are of the matrices $X$...
user41037's user avatar
1 vote
0 answers
100 views

Changing a nonlinear equality constraint into some conic inequality plus rank constraint

If we have a constraint optimization problem in which one of our constraint is $\prod\limits_{k = 1}^N {\left( {x - {a_k}} \right) = 0} $ . How could this nonlinear equality condition be changed into ...
Parsis's user avatar
  • 33
1 vote
0 answers
1k views

Diagonal entries of a Cholesky factorization

Let $I$ denote an identity matrix, $E$ denote the all-one matrix of dimension $k\times k$ and $c$ some positive real number. Define $X=B(I-cE)B^T$ where $B$ is given by $B:=\begin{pmatrix} 1 &\...
EEStudent's user avatar
0 votes
0 answers
52 views

What are the injective embeddings of R^d into the cone of (semi-) positive definite matrices of dimension d?

How can we characterize the set of all injective functions from $\mathbb{R}^d$ to the set of all symmetric positive definite matrices of dimension d?
Drmanifold's user avatar
0 votes
0 answers
51 views

Minimizer of forward and reverse Kullback-Leibler divergence with sum constraints on marginals

Consider minimization of the Kullback Leibler divergence between two discrete distributions $p$ and $q$: \begin{align*} D_{KL} \left( p \parallel q \right) = \sum_i p_i \log \left( \frac{p_i}{q_i} \...
TalTal The Eighth's user avatar
0 votes
0 answers
72 views

Minimizing the Spectral Norm of the Hadamard Product of a Quadratic Form Using CVX

I am trying to use CVX to minimize the spectral norm of the Hadamard product of two matrices, one of which is in quadratic form. Specifically, I am trying to minimize $\|{\bf A} \odot {\bf XX}^H\|_2$, ...
usergh's user avatar
  • 43
0 votes
0 answers
30 views

Application of greedy approach for optimization

I want to maximize an objective given by $$\max_{\{q_n,p_n\}} \sum_{n=0}^\infty (\alpha_1 - \beta_1 n) p_n + (\alpha_2 - \beta_2 n) q_n$$ where $\alpha_1 > \beta_1 >0$ and $\alpha_2 > \beta_2 ...
Prakirt Raj's user avatar
0 votes
0 answers
177 views

Given optimality of L1 norm, prove that absolute value of sum of a vector with proper sign is less than 1?

Problem: Given a domain $\mathcal{D}\subset\mathbb{R}^{l}$, we can find $l$ points $\boldsymbol{v}_{i}\in\mathcal{D}$, $i=1,\cdots,l$. Each point is a column vector with dimension $l\times1$. They ...
Justin's user avatar
  • 1
0 votes
0 answers
156 views

Optimal solution of complex optimization problem

Let $Q(x)=a(x)e^{jb(x)}$ be a complex function of $x$. We want to approximate this function with $R(x)=\alpha e^{jx\beta}$ such that \begin{align} \text{arg}\min_{\alpha,\beta} \int_{-\frac{A}{2}}^{\...
Math_Y's user avatar
  • 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 $\...
Math_Y's user avatar
  • 287
0 votes
0 answers
137 views

Any technique for linearization, or linear approximation?

Consider the following Matrix constraint: $$ \begin{bmatrix} -U+\psi\Sigma_b^{-1} & V \\ V^T & -V^TU^{-1}V+\tau_2 -\psi \end{bmatrix} \leq 0 $$ where $\Sigma_b$ is a known positive definite ...
Navid Hashemi's user avatar
0 votes
0 answers
41 views

Iterative algorithm for obtaining similarity

Let $x_1,x_2,\ldots,x_M$ be $M$ non-negative variables. Moreover, assume that $f_m(x_m)=\frac{x_m}{1+\sum_{n}\beta_{n}^{(m)}x_n}$ be $M$ fractional functions with non-negative constants $\beta_{n}^{(m)...
Math_Y's user avatar
  • 287
0 votes
0 answers
136 views

Finding a specific solution to $X^T\Sigma X = D$

I'm looking to solve for a specific $X$ in the following equation: $$X^T\Sigma X = D,$$ where $\Sigma \succ 0$, $D$ is a diagonal matrix with strictly positive entries, and all matrices are square. It ...
Allen94's user avatar
  • 41
0 votes
0 answers
121 views

Closed form solution to an equation

Let $X \in \mathbb{R}^{n \times d}, w \in \mathbb{R}^d, y \in \{\pm 1 \}^{n}, \alpha \in (0, 1)$. Consider the equation $$ X^{\top}(Xw-y)+\alpha \|w\|_{2}X^{\top}\operatorname{sign}(Xw-y)+\alpha\frac{...
user145905's user avatar
0 votes
0 answers
614 views

Hadamard / matrix product adjoint

First of all I would like to thank everyone over here at mathoverflow for their amazing generosity and help (for both pros and newbies like myself). I apologize if this question seems dumb; I'm a new ...
M.Salem's user avatar