Tagged Questions
0
votes
1answer
15 views
Notation minimum of a column vector
I'd like to know the notation to express the minimum of a column vector.
Is this notation correct?
\begin{equation}
\min
\left[\matrix{
\left|b_{n}-b_{n+1}\right| \cr
...
2
votes
1answer
32 views
Ask a question about an example in a course note on optimization problem with equality constraint
I have two difficulties on understanding the solution to an example in a course I took this semester on optimization. This example is given to illustrate the usage of Lagrange multiplier method ...
0
votes
1answer
20 views
Efficient (approximate) projection onto the special orthogonal group
I need to carry out an optimization on the special orthogonal group $SO(n)$. For the line search I use a simple back-projection method
$$\mbox{minimize}_\tau f(\pi(X+\tau Z))$$
where $X\in SO(n)$ ...
0
votes
1answer
72 views
Difference between maximizing matrix's $l1$ norm and Frobenius norm
The original problem is to maximize the Frobenius norm of a matrix product
$max_{X\in \mathbb{D}}||B^TXA ||_F$, $\mathbb{D}$ is the doubly stochastic matrix set
As this is too difficult due to ...
0
votes
2answers
45 views
Transpose of matrix inverse: $(AA^T)^{-1}A^Tb \stackrel{?}{=} (A^TA)^{-1}A^Tb$
Given the matrix equation:
$$ x^TA^TA = b^TA $$
I'm trying to find the least squares solution (i.e.; trying to minimize $r=||Ax-b||$). The matrix $A$ is not necessarily symmetric.
When I solve it ...
2
votes
0answers
40 views
Use of low rank approximation of a matrix
I am trying to figure out why do we need a low rank approximation of a matrix. Why is it used and where? Any insights?
0
votes
1answer
75 views
Solve: This System of equations for $X$ (does a real solution, exist?)
How can I solve $AX + diag(X)[I-c]=0$ for $X$?
All matrices have real entries, $diag(X)$ is a diagonal matrix with the diagonal entries being the diagonal entries of $X$, and $c$ is a constant, real ...
0
votes
2answers
51 views
Is this a linear programming problem?
So I'm trying to solve this problem.
We are given an image ( a two dimensional matrix ).
The image is all white except for some red dots. We are given the list of the red dots ( (X,Y) pairs ). The ...
3
votes
2answers
124 views
Solution of a Sylvester equation?
I'd like to solve $AX -BX + XC = D$, for the matrix $X$, where all matrices have real entries and $X$ is a rectangular matrix, while $B$ and $C$ are symmetric matrices and $A$ is formed by an outer ...
1
vote
3answers
109 views
A constrained linear least Frobenius norm problem:$\min_{X} \|A-XB\|_F$ subject to $Xv=0$?
Assume we are given two matrices $A, B \in \mathbb R^{n \times m}$ and a vector $v \in \mathbb R^n$. $\|\cdot\|_F$ is the Frobenius norm of a matrix. How can we solve
$$\min_{X \in \mathbb R^{n ...
0
votes
1answer
24 views
inequalities for optimization over psd matrices with constraints
Consider two p.s.d. matrices $A$ and $B$ both in $\mathbb{R}^{d \times d}$. Define $$a = argmax_{x \in \mathbb{R}^d} x^\top A x $$ and $$b = argmax_{x \in \mathbb{R}^d} x^\top B x $$ both subjected to ...
2
votes
0answers
32 views
maximal m-elements of the matrix inversion
Suppose the $n\times n$ matrix $A$ is invertible, and all its elements are between 0 and 1. The existing matrix inversion operation of $A^{-1}$ will take $O(n^3)$ time. Now I just want to find the ...
2
votes
0answers
144 views
Optimization problem about large matrices
I'd like to solve the following optimization problem:
Find non-negative scalar $a$, $b$, $c$ to minimize
$\| (D-(aA+bB+cC+D^{-1})^{-1})y\|^2+2\operatorname{trace}((aA+bB+cC+D^{-1})^{-1})$
where ...
0
votes
0answers
44 views
Matrix Partioning with number of rows being optimized.
Given a ternary matrix G which is an N*M matrix with values containing all entries 0,1,2.
Is there a methodology/algorithm wherein we could write another binary matrix H of dimension 2N*M such that ...
2
votes
5answers
188 views
How to minimize $\| y- Ax\|$ subject to $\|x\|=1$ and $x \geq 0$?
Given $y \in \mathbb R^n$ and $A \in \mathbb R^{n \times n}$, whis is some way for
$$\min_x \| y- Ax\|$$ subject to $\|x\|=1$, and $x \geq 0$ (which means every components of $x$ is nonnegative)?
...
1
vote
2answers
121 views
Linear optimization problem: Minimizing a linear function over an affine set.
The problem is as follows:
Give an explicit solution of the linear optimization problem below.
$$
\text{minimize}\ c^Tx \\
\text{subject to}\ Ax\ =\ b
$$
No other information is given.
My ...
1
vote
1answer
239 views
Armijo's rule line search
I have read a paper (http://www.seas.upenn.edu/~taskar/pubs/aistats09.pdf) which describes a way to solve an optimization problem involving Armijo's rule, cf. p363 eq 13.
The variable is $\beta$ ...
2
votes
0answers
64 views
Binary optimization
Let me first make my background clear. I am a PhD student with not much knowledge in optimization but I need to do some optimization as a part of my research work. My problem is as follows:
There are ...
2
votes
1answer
62 views
Proof: Ratio of matrix traces and difference of traces
$\newcommand{\Tr}{\operatorname{Tr}}$
Am looking for a proof that shows that the minimization of $\frac{\Tr X^TAX}{\Tr X^TBX}$ is equivalent to the minimization of $\Tr X^TAX-\lambda \Tr X^TBX$ for ...
0
votes
1answer
62 views
Minimization to Maximization doubt in SVM
I came across a lecture on Support Vector Machines and in the lecture they converted a maximization problem into a minimization problem. I am wondering how it was done...
$
Max \frac {1}{||x||}
$
...
1
vote
2answers
249 views
derivative of a determinant of a matrix with respect to an element that appears many times in the matrix
I've been trying to find material on matrix calculus but it seems hard to find ones with understandable proofs.
I'm doing research work and I am trying to verify some computation. Suppose that I have ...
3
votes
2answers
67 views
Quadratic function values through iterative updates
Suppose a function $$f(x)=\frac{1}{2}x^TAx-b^Tx$$ is given, for some symmetric $A\in\mathbb{R}^{n\times n}$ for which all off-diagonal entries of A are nonpositive, and every diagonal entry of A is ...
1
vote
0answers
34 views
Optimizing a matrix
input: $b_1,b_2,...,b_n$ positive integers.
$a_1<a_2<...a_n$ positive integers
output: positive integer
I'm given
$b_1$ columns of the form
...
0
votes
0answers
38 views
Another Matrix Algorithn
Another Matrix algorithm
input: $b_1,b_2,...,b_n$ positive integers.
$a_1<a_2<...a_n$ positive integers
output: positive integer
I'm given
$b_1$ columns of the form
$ \left( ...
0
votes
1answer
56 views
Optimize the matrix of “mis-ties” by adding|subtracting a number to|from a whole row|column
Preface:
There is a net of $N$ almost-straight paths on an aerial map. Some of them intersect with another. At the points of intersection there are possibly a "mis-tie", which is expressed as a ...
2
votes
2answers
75 views
A Quadratic Problem (which looks very simple)
This arises as a part of my work.
\begin{align}
\min_{x^{H}x=1}~&x^{H}A_1x \\
subject~to~&x^{H}A_2x=0
\end{align}
$A_1$ and $A_2$ are $N\times N$ hermitian matrices and $x$ is a unit norm ...
0
votes
1answer
46 views
Feasibility of a given set of Quadratic Forms
This arises as a part of my work. Given a positive number $t$, two hermitian matrices $P_1$ and $P_2$, I am interested in knowing if a unit norm vector $z$ exists such that
\begin{align}
...
2
votes
0answers
35 views
Graph of a set homeomorphic
I would like to please guide me on this question:
Let $S_+$ denote the set of semi positive definite matrices in $\mathbb{R}^{2\times 2}$ is known that $S_+\subseteq Sym \simeq\mathbb{R}^{3}$,wherein ...
2
votes
1answer
80 views
Unimodular matrix definition?
I'm a bit confused. Based on Wikipedia:
In mathematics, a unimodular matrix M is a square integer matrix
having determinant +1, 0 or −1. Equivalently, it is an integer matrix that is invertible ...
1
vote
1answer
35 views
vector optimization
Trying to solve for (vertical) vector $β$ of length $n$, that maximizes scalar function $f(β)$
$$f(\beta) = \frac{\beta^T \mu}{\sqrt{\beta^T M \beta}}$$
where $μ$ is a (vertical) vector of length ...
2
votes
1answer
296 views
How to convert quadratic programming problem to matrix form
I am new to this topic and am looking at an example I can't figure out. Can someone please help explain how this example creates the matrices used in the solver? Thanks!
This is the PROBLEM
...
1
vote
1answer
42 views
General solvability at the stationary condition
Suppose a convex quadratic function $f(x)$ is given. To find a minimum of such function, one sets its derivative so zero, and solves for $x$. For instance, suppose that the result of differentiation ...
2
votes
1answer
86 views
Positive values for a set of quadratic forms of Hermitian Matrices. (To find a set of vectors in which a hermitian matrix is positive definite)
Assume all matrices I discuss about are $N \times N$ and the vectors conform with dimensions. Consider the following set of Quadratic inequalities where all the matrices $A_i$ are hermitian.
...
0
votes
0answers
27 views
Eigen Values of Hermitian Matrices and some lower bounds on Unnormalized Rayleigh quotient
I have a Optimization problem of the form
\begin{align}
\min &x^{H}Qx \\
\text{subject to}\quad &x^{H}A_{i}x\ge c_{i}\quad \forall i\in\{1,2\ldots, N\}
\end{align}
All matrices are complex ...
0
votes
1answer
59 views
Minimum value of an inner product
Suppose $A$ is a positive definite $n \times n$ matrix over complex numbers.
Then we know that $<Av,v>$ has minimum value $0$, when $v=0$.
Now suppose $v$ is constrained so that the first $k$ ...
2
votes
1answer
176 views
Symmetrically make this matrix orthogonal, but don't you dare use the Frobenius norm…
I have read many of the questions already here in regards to the Frobenius norm, but they do not help me too much.
My question is, why is the Frobenius norm not considered a 'proper' norm?
In a ...
2
votes
0answers
47 views
Root Convergence rate of Iterative Scheme [closed]
I have an iterative sequence for optimizing an EM algorithm based loss function $L(X)$ with $t$ being the iteration number as:
$X_t=ABX_{t-1}+CX_{t-1}+X_{t-1}$ where $A$ is a diagonal matrix, $B$ and ...
1
vote
1answer
70 views
Lower bound of $J=\frac{x^TAx}{x^TBx}$
Consider two symmetric positive semi-definite matrices $A, B \in \mathbb{R}^{n\times n}$.
Suppose that $A$ and $B$ have the same null space $\mathcal{N}\subset \mathbb{R}^n$.
Now consider the ...
0
votes
0answers
20 views
Does post-processing of NMF output preserve the objective function value inequality?
Assume $F,B$ are fixed and my function is $O(C) = \frac{1}{2} ||F-BC^T||^2_F$.
I know that $O(C_1)<O(C_2)$. Now, if i do same post processing on columns $C_1$ and $C_2$, for example, entries in the ...
1
vote
2answers
121 views
What algorithms and/or software libraries should I use to solve this?
I'm trying to write simple data format recognition program (that shows "what things does this unknown uncompressed unencrypted file have inside and where that things are located in the file") and it ...
4
votes
2answers
184 views
Nearest matrix in doubly stochastic matrix set
Suppose $\mathcal{D}_N$ denote an $N\times N$ doubly stochastic matrix, given any element $M\in \mathcal{D}_N$ , the singular value decomposition for $M$ is $$ M=USV'$$
where $U$ and $V$ are two ...
1
vote
1answer
150 views
Minimising a matrix equation to find 'best fit' affine matrix
Here is my problem:
I have an image divided into segments. Each segment consists of pixels with coordinates (x,y) called vector $v$, each pixel has a length 3 vector RGB called $I(v)$. I want to ...
2
votes
1answer
178 views
Proof of Non-Convexity
Am looking for a proof of non-convexity of the quotient of two matrix trace functions as given by $\frac{\operatorname{Tr}X^TAX}{\operatorname{Tr}X^TBX}$, when $TrX^TBX>0$
for two different ...
0
votes
0answers
71 views
Does a single Gauss-Seidel iteration lead to unique coordinates?
I managed to reduce certain computational problem to the Gauss-Seidel solution of the following linear system: $$Ax=Ly,$$ where $A, L\in\mathbb{R}^{n\times n}$, and $x,y\in\mathbb{R}^{n\times 2}$ are ...
0
votes
0answers
43 views
Maintaining the line with the 2D iterands
Suppose a linear system is given
$$AX=B,$$
where $A\in\mathbb{R}^{n\times n}$ is a symmetric strictly diagonal matrix, and $X, B\in\mathbb{R}^{n\times 2}$. Therefore, the 2D Jacobi iterative solver is ...
1
vote
0answers
337 views
Efficient Cholesky decomposition of inverse matrix
I want to generate random numbers from a multivariate normal distribution in Matlab. Normally, this is done like:
$w = \overline{w} + \text{chol}(\Sigma) \cdot \vec{l}$
But in my case I don't know ...
3
votes
2answers
125 views
No identical rectangles in a matrix
I have a matrix of dimensions N x M.
Every cell has an integer.
Now, I want for every 'rectangle', to verify that all its corners are not the same.
Example:
This matrix is fine:
This matrix is not:
...
0
votes
1answer
105 views
Correctly adding constraints to Ax=b
I have a function of the form
$$
E(\mathbf{x})=E_1(\mathbf{x})+E_2(\mathbf{x})
=\sum_i\|\ldots\|^2+\sum_j\|\ldots\|^2
$$
and want to solve the optimization problem
$$
...
0
votes
1answer
52 views
Optimisation Problem
I'm given a lattice with particles having charges which have known magnitude but unknown signs. The primary aim is to stabilize the lattice (or decrease the force acting on the system) by assigning ...
2
votes
2answers
163 views
On sums of unitary matrices
Let $J$ be the $n$ by $n$ matrix of all 1's. Let $f(n)$ be the least number $m$ of unitary matrices $U_1,\dots,U_m$ so that $J = U_1 + \cdots + U_m$. What can you say about the growth of the function ...
