All Questions
Tagged with linear-algebra convex-optimization
121 questions
1
vote
1
answer
877
views
Minimization problem involving the inverse of an affine matrix function
I want to minimize $v^T (A+I+UQU^*)^{-1} v$, subject to $Q$ and $A$ being positive semi-definite and ${\rm trace}(Q)<1$. Here, $v$ is a given vector with unit norm, that is, $\|v\|_2=1$.
- 377
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 , ...
- 88
3
votes
1
answer
275
views
Uniqueness of l1 minimization
Let $A \in \mathbb{R}^{m \times n}$.
Is it true that $$\min \limits_{Q \in \mathbb{R}^{n \times m}}|I - QA|_{\infty} < \frac{1}{2}$$ is criteria for the uniqueness of the 1-sparse solution to
$\...
- 33
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} &...
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$ ...
- 13.9k
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)$...
- 275
4
votes
2
answers
734
views
Fast projection onto a subspace
Given an $n$-dimensional vector $\mathbf{c}\in [0,1]^n$, let $\Delta_{\mathbf{c}}$ be the set of points $\{\mathbf{x}\in [0,1]^n: \langle \mathbf{c},\mathbf{x} \rangle \le 1\}$, where $\langle \mathbf{...
- 1,677
6
votes
2
answers
875
views
Is there any efficient solution of the matrix equation AXB + (AXB)' + cX = D
I am trying to find the symmetric solution $X\in \mathbb{R}^{p\times p}$ of following matrix equation:
$AXB + (AXB)^T + cX = D$
where $A,B\in \mathbb{R}^{p\times p}$ are symmetric positive ...
- 89
2
votes
2
answers
276
views
Is this parametrized semidefinite program convex?
I am considering an optimization problem of the form:
\begin{equation}
\begin{split}
f(s) &= \min_{X} \mathrm{tr}(C(s)X) \\
&\;\;\;\;\;\;\;\;\;\;\; X \ge 0, \\
&\;\;\;\;\;\;\;\;\;\;\; \...
- 101
2
votes
1
answer
255
views
Efficient algorithm for solving a convex quadratic program [duplicate]
Let $A \in \mathbb{R}^{n \times m}$ and $b \in \mathbb{R}^n$. Suppose $m \ll n$. How to solve this quadratic program efficiently?
$$\min_{x \in \mathbb{R}^n} \frac{1}{2} x^\top AA^\top x + b^\top x$$
- 422
-1
votes
1
answer
137
views
Does a half plane contain intersection of some other half planes? [closed]
I'm doing research in Optimization and I have found this obstacle in the way.
If we have set of half planes like $c_ix\leq b_i$ where $i\in \{1,\ldots ,k\}$ there is an algorithm(it would be better ...
- 19
1
vote
1
answer
291
views
Norm of solution of quadratic program
In a quadratic program (QP), do linear equality constraints always reduce the norm of the minimizer? Specifically, let $P \succ 0$, $A \in \mathsf{M}_{m\times n}$ and $q\in\mathbb{R}^n$. Define
$$x^* ...
- 153
2
votes
2
answers
99
views
Extremal Covariance Duality
Given real vectors $v$ and $r$ of the same size, what are the following?
$\inf\{v'R^{-1}v ~ \colon ~ R>0 \, , \, \text{diag}(R)= r\}$
$\sup\{v'Rv ~ \colon ~ R>0\, , \, \text{diag}(R)= r\}$
...
- 81
0
votes
1
answer
917
views
What is the most accurate and efficient method of finding an inverse of a hessian matrix?
For any hessian matrix, of say 300 by 300, and may or may not necessarily be positive semi-definite, thus algorithms such as Cholesky decomposition may not be used.
I've found that some algorithms ...
- 17
8
votes
3
answers
2k
views
Optimization problem with determinant as objective
Let $A$ be a given symmetric positive definite $N\times N$ matrix. I need to find a symmetric positive semi-definite matrix $S$ which is the solution to the following optimization problem
\begin{align}...
- 1,421
4
votes
1
answer
456
views
Least square solution to $AXB+CXD=E$
I am trying to find the least-squares solution $X$ of the following matrix equation
$$AXB+CXD=E$$
Of course, I know that this equation can be written in the form
$$(B^T \otimes A+D^T \otimes C) \...
- 191
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 (...
- 21
2
votes
1
answer
226
views
Tighest Gap $\|x\|_1/\|x\|_2$ between $\ell^1$ and $\ell^2$ norms
I'm looking specifically at the optimization problem
$$
\begin{align*}
\text{maximize: }& n - \frac{\|\lambda\|_1^2}{\|\lambda\|_2^2}\\
\text{subj. to: }& \lambda \succeq \epsilon\mathbf{1}
\...
- 153
4
votes
3
answers
283
views
Iterative matrix inversion with $L^\infty$ norm
The usual conjugate gradient type algorithms for iteratively finding the inverse of a matrix applied to a vector, $x = A^{-1} y$, works by minimizing $\|Ax - y\|^2$ where $\| \cdot \|$ is the $L^2$-...
- 1,150
7
votes
1
answer
373
views
Is the solution of this optimization problem always positive semidefinite?
We are given a set of unit vectors $U \subset \mathbb{C}^n$ which spans the space $\mathbb{C}^n$. Given another unit vector $x$, consider then the following optimization problem:
$$ \sup_H \left\{ x^*...
- 73
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$
$$\...
- 153
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 ...
- 263
3
votes
1
answer
154
views
Solving Matrix/Operator Equation $H P X + X P H + HQ = 0$
This problem arises when minimizing the operator equation $X P X^* + X Q + R$ over positive $X$ with respect to the positive cone on a Hilbert space $\mathcal{H}$.
The (reduced) task:
Given $P$ and $...
- 153
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 ...
- 6,853
2
votes
1
answer
585
views
A problem about convex optimization and trace of symmetric matrix
Please prove or disprove that, for symmetric matrix $A=A^T$, we have
$$\max_{x \in \{\pm 1\}^n} x^T A x \geq \mbox{Tr}(A)$$
- 21
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{...
- 129
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 ...
- 2,207
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)...
- 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 ...
- 710
6
votes
1
answer
4k
views
Complexity for solving linear equations?
What is the best known complexity for finding a vector $x \in \mathbb{R}^n$ to minimize $||Ax - b||^2$ and/or to solve (when possible) the system of linear equations $Ax=b$?
I am interested in ...
- 544
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 ...
- 7,182
8
votes
1
answer
2k
views
Finding Toeplitz matrix nearest to a given matrix
For an arbitrary $N\times N$ Hermitian matrix $A$, I want to derive a Toeplitz matrix from $A$ such that the eigenvectors of both matrices have minimal change.
Specifically I want find the Toeplitz ...
- 495
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 & \...
1
vote
1
answer
169
views
On optimizing a function whose projection and projected vector go through a linear transformation
Assume the two sets of vectors $\{\mathbf{a}_1,\ldots,\mathbf{a}_N\}$ and $\{\mathbf{b}_1,\ldots,\mathbf{b}_N\}$ of equal length. My goal is to find the optimum matrix $\mathbf{C}$ to the following ...
- 345
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$...
- 45
6
votes
2
answers
5k
views
Minimize Frobenius norm
My question is the following:
Suppose $M$ is an $n \times n$ symmetric real matrix. I want to find an $n \times n$ symmetric real matrix X such that $|| X -M||_F$ is minimized with the constraint ...
- 263
1
vote
2
answers
151
views
Sensitivity analysis in minimum norm problems under a linear constraint
Suppose $\Delta$ is some nice topological space, say compact, and Hausdorff.
Let $A:\Delta \rightarrow \mathbb{R}^{m\times n}$ be a continuous $m\times n$ matrix valued map. Let $b\in \mathbb{R}^{m}$ ...
- 11
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-...
- 121
4
votes
0
answers
205
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) = \...
- 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 ...
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) ...
- 695
3
votes
1
answer
775
views
Is there some quantitative version of interlacing of eigenvalues of a matrix under rank-1 update?
Given a real symmetric matrix $A$ and a vector $v$ of the same dimension we know that the eigenvalues of $A + vv^T$ are left interlaced by the eigenvalues of $A$.
But do we have any quantitative ...
- 1,893
3
votes
1
answer
660
views
Condition number after preconditioning
Suppose $A$ and $P$ are symmetric, positive definite matrices and that we factor $P^{-1}=EE^\top.$ Is it true that the condition number of $PA$ is upper-bounded by the condition number of $E^{-1}AE^{-...
- 705
7
votes
2
answers
251
views
What methods do we have to understand the spectrum of matrices with restricted entries?
Consider questions of the form (or the "most probable value of" version of these questions rather than the "largest possible"),
What is the largest possible spectral radius of a $...
- 1,893
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 ...
- 1
5
votes
1
answer
955
views
Maximizing Frobenius Norm of Commutator (an opposite Procrustes problem)
I was wondering if anybody has any suggestions on the following problem:
Let $S$ be an $n\times n$ positive definite symmetric matrix. I wish to find an $n\times n$ orthogonal matrix $R$ which ...
- 617
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 ...
- 13.9k
8
votes
3
answers
526
views
Lower bound for spectral radius on $\operatorname{GL}(n,\mathbb{Z})$
Consider the group of matrices $G =\operatorname{GL}(n,\mathbb{Z})$ with integer entries and determinant $\pm 1$. For each matrix $D \in G$, the product of the eigenvalues of $D$ is equal to $\det D =\...
- 345
0
votes
1
answer
246
views
Matrix equation
Let $A$ be $k\times n$ matrix i.e., $A=(a_{1},\ldots, a_{n})$ where $a_{j} \in \mathbb{R}^{k}$, $rank(A)=k$ and $1\leq k \leq n$. Let $q=(q_{1},\ldots, q_{n})\in\mathbb{R}^{n}$ be such that $0<q_{j}...
- 3,946
2
votes
2
answers
352
views
The set of matrices with same spectral radius
I am working on an optimization problem over the set of positive matrices (that is, matrices where all entries are positive numbers) that have the same spectral radius. My main problem is how to ...
- 51