All Questions
6,252 questions
0
votes
0
answers
68
views
Estimate bounds on Minkowski distance from point to a segment in Lp space
Assumptions
Let
$L_p(x,y)=(\sum_i|x_i - y_i|^p)^{1/p}$ (Minkowski metric),
$a,b$ be arbitrary $n$-dimensional points,
$c$ be a point that satisfies $L_p(a,b) = L_p(a,c) + L_p(c,b)$, i.e., a point ...
- 101
0
votes
1
answer
270
views
Generalized assignment problem with no integrality gap
Suppose I am solving the generalized assignment problem, so that I
am given matrices $U$ and $W$ and a vector $c$ (all three of which
have, say, positive entries), and I want to solve
$$\text{...
0
votes
0
answers
163
views
Applying a linear operator to a basis set following SVD orthonormalization
Define $\Phi$ as an $N$x$N$ dense, symmetric matrix, who's columns represent a set of $N$ non-orthogonal bases.
My intention is to:
decompose $\Phi$ via SVD:
$U \Lambda V^T = \Phi$
to create it's ...
- 1
0
votes
0
answers
80
views
Finding gradient of an optimization
I am trying to find the gradient of the following optimization problem and then add to objective, but I got some trouble in computing. Could you please help me?
Assume that we have an optimization ...
- 161
0
votes
0
answers
81
views
A Optimization problem using co-ordinates of joint numerical range.
Let $\mathbf{A}_1,\dots,\mathbf{A}_L$ be $N\times N$ hermitian matrices. Define the mapping from the $N-$dimensional unit sphere to $\mathbb{R}^L$ as
\begin{align}
\mathcal{S}=\{\left(\mathbf{u}^H\...
- 1,421
0
votes
0
answers
694
views
Heat equation with graph laplacian
I would like to start with considering the time-dependent heat equation on a connected graph and consider its Laplacian matrix.
Suppose we have a connected graph with unknown temperature on vertices. ...
- 161
0
votes
0
answers
103
views
Perturbed linear system, particular form
We have a linear system $Ax=b$ where $A$ is real and symmetric, all elements of its main diagonal are strictly positive and all off-diagonal elements are $\leq 0$. Further, $A_{ii} > -A_{ij} \; \...
- 311
0
votes
0
answers
917
views
Inverse problem with a rank-1 update
I hope you can help me out with this. I have to find the solution x to an inverse system
$$
x=A^{-1}b
$$
This inverse problem is basically a least square problem with a rank-1 update.
$$
x=[uv^{T}...
0
votes
0
answers
91
views
Complexity of turning a d-degree polynomial to 2-degree polynomial
For a very simple example,
$(1+x)^4=x^4+4x^3+6x^2+4x+1$ is a 4 degree polynomial, and I want to change it to a 2-degree polynomial by add more variables, for this example, we can simply let $y=x^2$, ...
- 187
0
votes
0
answers
251
views
Sparse matrix factorization of a rank deficient matrix by decomposition into linearly independent components
I've got a little conjecture I need to prove for a theoretical result related to causal Bayes net search with latent variables under sparsity constraints. If you're interested in the application ...
- 11
0
votes
0
answers
561
views
What are the properties of this linear operator?
Suppose $f(x)$ is a function which satisfies the following condition:
$$f(x)=\sum_{k=0}^\infty G(2k)\frac{x^{2k}}{(2k)!}$$
Where the generating function $G(x)$ is a "natural" or "discrete-analytic" ...
- 10.1k
0
votes
0
answers
131
views
The largest size of a boolean subgraph (a hypercube) of a given graph
Let $G(\mathbb{F}_2^n)$ denote the graph that represents the lattice of all subspaces of $\mathbb{F}_2^n$ (also called a Hasse diagram). I am interested in knowing if there exists a large hypercube ...
- 313
0
votes
0
answers
49
views
Forming orthogonal bases in different orders
Let $\alpha_1, \dots, \alpha_n$ be unit vectors in some vector space $V = R^d$. For any permutation $\pi: [n] \rightarrow [n]$, we can form the Gram-Schmidt orthogonal bases $\beta_{\pi,1}, \dots, \...
- 3,475
0
votes
0
answers
104
views
Linear system with many solutions from a finite set
Basically I am looking for a linear system with
many solutions from a finite set.
Choose a finite set of rationals $S$ and fix
positive integer $k$.
Let $A$ be a linear system with $n$ variables $...
- 25.4k
0
votes
0
answers
320
views
Invariants of the Determinant Form
Consider a form of degree $r$ in $n$, that is, a homogeneous polynomial
$$f(x_1, \ldots, x_n)=\sum_{i_1+\ldots i_n=r}\alpha_{i_1 ... i_n}x_1^{i_1} ... x_n^{i_n}
$$
After the linear change of ...
- 801
0
votes
2
answers
153
views
Union of linear inequalities cover whole space?
We have $n$ variables $a_0,a_1,\ldots,a_n$ such that $a_i\geq a_{i+1}$.
There are $k$ sets of linear inequality constraints on the $a_i$.
I need to check that any choice of $a_i$ satisfies at least ...
- 109
0
votes
0
answers
117
views
"Almost orthogonalizing" matrices using a signature matrix
Suppose $A$ and $B$ are two real symmetric $n \times n$ matrices (If simpler, consider $A$ and $B$ to be 0/1 matrices, say, adjacency matrices of d-regular graphs).
Then $||AB||_{op} \leq ||A||_{op}||...
- 949
0
votes
0
answers
704
views
expected matrix inverse of circulant plus diagonal matrix with chi-square variables
Let $R$ be a semi-definite $N\times N$ circulant Toeplitz matrix and let $N\to \infty$.
Let $D$ be an $N\times N$ diagonal matrix where the elements on the main diagonal are independent chi-square ...
- 96
0
votes
0
answers
115
views
a very elementary question on the conjugated matrices
Let $A$ and $B$ two matrices in $GL_{n}(K[[\pi]])$, regular semisimple on $GL_{n}(K((\pi)))$, with $K$ an algebraically closed field of characteristic zero .
We suppose that they have the same ...
- 3,472
0
votes
0
answers
266
views
Finding the effective maximum number of subspaces in a finite dimensional vector space
Hi mathoverflow community, may be some one may give me a hint on the following problem before I spend much time on brute force search.
For $q$ a prime number and $n=6$, let $\mathbb {F}_{q}^{n}$ be ...
0
votes
0
answers
262
views
Lattice basis reductions and finding minimal values
While reading several articles about lattice basis reduction I am left with a few questions.
For one, I came across this piece of text
Let $\alpha$ and $\beta \in \mathbb{R}$. Also let $X>0$ and $...
- 1
0
votes
1
answer
311
views
Subspace generated by positive vectors
Hi everyone, first of all i must admit i'm very familiar with quadratic forms and positive subspaces, so i'm sorry if my question is too trivial. So, here's my problem:
Let $L$ be a real vector space ...
0
votes
1
answer
775
views
Positive subspaces of quadratic forms
here's my question:
Let $V$ be a k-dimensional vector space over $\mathbb{R}$ and $q$ a quadratic form on $V$ of signature $(m,n)$ , $m+n=k$.
We have $W\subset V$ a positive (with respect to the ...
0
votes
0
answers
957
views
Diagonal of the inverse of a 6x6 symmetric partitioned matrix
Let
$$M = \begin{bmatrix}
A & B \\
B & C
\end{bmatrix}$$
in which $A$, $B$ and $C$ are $3 \times 3$ matrices being also symmetric. In fact, they are quite similar, just differing on a single ...
- 1
0
votes
0
answers
52
views
Dense Matrix Estimation
I have a matrix $X \in \mathbb{R}^{m\times n}$ and I want to estimate it with a dense matrix $Y^{m\times n}$ such that $Y$ is still close to $X$ in some distance measure. Is this doable in a ...
- 137
0
votes
0
answers
104
views
Big eigenvalues of a special stochastic matrix
Given a matrix $M$ of size $n\times n,$ we write its different eigenvalues by $x_1,x_2,\ldots,x_m$ with $m\leq n$ such that $|x_1|>|x_2|>|x_3|>\cdots|x_m|,$ and call $x_2\doteq |\lambda_2|(M)....
- 105
0
votes
0
answers
146
views
Global solution for spectral clustering
I used spectral clustering for directed graphs suggested by Dengyong Zhou paper to partition the graph.I selected the eigen vectors corresponding to k largest eigen values and then I use kmeans or FCM ...
- 13
0
votes
1
answer
312
views
Deriving the fundamental equation (with regards to computer vision)
I'm having a hard time understanding how a few equations are being derived. So the fundamental equation is an equation that relates corresponding points in stereo images. Anyway, that's the basic ...
0
votes
0
answers
270
views
Solution Existence of a System of Complex Quadratic Equations
Consider $ {x_k}_{k = 1}^K \in \mathbb{C}^{N \times 1}$ a set of $K$ complex vector variables of length $N$. I am interested in finding the existence of a solution of the following
quadratic set of ...
- 342
0
votes
0
answers
257
views
What is the integer form of a projector into the intersection of the ranges of two integer projection matrices?
Consider two square integer matrices $X$ and $Y$ of the same dimension with the following properties:
$X^2=rX$, and $Y^2=sY$ for integers $r$ and $s$. The $\gcd$ of the entries of $X$ is 1 and the $\...
0
votes
0
answers
155
views
Convexity of a Certain Set of Covariance Matrices
Hello,
My question is about a certain set of matrices being convex or not. I'll start with some preliminaries in order to define myself properly. Let $X_1,U,X_2$ be three zero-mean Gaussian random ...
- 155
0
votes
0
answers
151
views
Ratio of Eigen values and Mutual Independence
Given a matrix $X$. Calculating the Eigen values of $XX^T$ and using the ratio of maximum and minimum eigen values normally gives the condition number of the matrix.
If $X$ contains $M$ observations ...
- 1
0
votes
1
answer
590
views
Strictly diagonally dominant hermitian matrices eigenvalues sign
Let $A\in \mathcal{M}_{n\times n}(\mathbb{C})$ be a strictly diagonally dominant hermitian matrix.
My main goal is to tell how many positive eingenvalues $A$ has in terms of its leading diagonal ...
- 3
0
votes
0
answers
166
views
Do the Eigenvectors find by use PCA on a set of data point, a good replacement for Random Projection when I later on use L1Magic to reconstruct the sparse vector?
Concretely if I use the first k eigenvectors find by PCA with a point set A,to project another sparse vector b to k dimension subspace, then use L1-magic to recover b. Will this be better than a ...
- 87
0
votes
0
answers
237
views
Geometric Mean of Positive Matrices
Hello all,
My question regards the geometric mean (GM) of two positive matrices. The definition of the GM for two positive matrices $(A,B)$ is given by:
$M_0(A,B)=A^{\frac{1}{2}}(A^{-\frac{1}{2}}BA^{-...
- 155
0
votes
0
answers
224
views
When does a real-valued function of a matrix depend only on eigenvalues?
Let $\mathcal{N}$ be the space of all $n \times n$ matrices that are similar to some nonnegative matrix with zero diagonal and let $f: \mathcal{N} \to \mathbb{R}$ be a continuously differentiable ...
- 1,068
0
votes
0
answers
244
views
Checking whether this would be bounded
It may be better to post this question here. Assume that $M$ is an $m$ by $m$ ($m$ is an even number) symmetric
positive-semi-definite matrix with exactly $m/2$ positive eigenvalues
and every entry of ...
- 1
0
votes
1
answer
2k
views
Finding linearly independent columns of a large sparse rectangular matrix
I have a problem that necessitates solving a large non-negative least-squares
problem. My matrix A is large, sparse, highly rectangular (num rows >> num cols)
and nearly binary. However, A is not ...
- 103
0
votes
0
answers
103
views
Gauss-Newton for quotient functions
I'm optimizing a function of the form
$$
\sum \frac{ \|\mathbf{f_i}(x)\|^2 }{ g_i(x)^2 + h_i(x)^2 }
$$
where $x$ is a real vector, $\mathbf{f}(x)$ is a real vector, and $g(x)$ is a scalar. My first ...
- 561
0
votes
0
answers
324
views
Changing basis on an extension of a free Z-module.
Consider a finite-rank free $Z$-module $Y$. Let $c: Y \times Y \rightarrow Z$ be a $Z$-bilinear form. Assume that $c(y_1, y_2) + c(y_2, y_1)$ is even, for all $y_1, y_2 \in $. Then $c$ "incarnates"...
- 13.3k
0
votes
0
answers
154
views
linsolve derivative
Consider a vector $\mathbf{g} \in \mathbb{R}^{m}$ and a matrix $\mathbf{A} \equiv \mathbf{A(g)} \in \mathcal{M}_{p\times q} \[\mathbb{R}\]$, a function of $\mathbf{g}$.
Furthermore, let $\mathbf{S} \...
0
votes
0
answers
194
views
A linear program related question
Dear all, recently, I encountered the following problem. It is closely related to the order of growth for UMD constants of all $n$-dimensional Banach lattice.
Let $\alpha^k \in (\alpha_1^k, \alpha_2^...
- 769
0
votes
0
answers
79
views
Computing maximum point for minimal function of a family of linear functions
Let $x \in S^n $ where $S^n = ${$ [x_1,x_2,...,x_{n+1}]\in \mathbb{R}^{n+1} \mid x \ge 0 , \sum x_i = 1 $} and let $f_i : I^n \to \mathbb{R}$ be a finite $m$-sized family of LINEAR functions such that:...
- 11
0
votes
0
answers
204
views
Matrix Mutiplication through Matrix Logarithms and Exponentials
Let $A,B$ be full rank $n \times n$ matrices. If $AB = BA$, then $\exp(\log(A)+\log(B))=AB$.
Supposing $A = USL$ and $B = VSL$ where $U,V,S,L$ are integer valued matrices, $det(L)=1$ and $U = LVL^{-1}...
- 13.9k
0
votes
0
answers
783
views
LP relaxation for ILP\IP (integer linear programming)
I am familiar with LP relaxation for ILP (or IP). Assume we concern with integer minimization problem, which we formalize using ILP; we then relax the ILP into LP and we say that the LP provides a ...
0
votes
0
answers
161
views
vector equation
Suppose you have an equation of the form $Hx=Ky$, where $x,y$ are vectors of length $n,m$ respectively ($m>n$) and $H,K$ are matrices of orders $n \times n,n \times m$ respectively. Is there some ...
- 6,962
0
votes
0
answers
138
views
Approximation of large dimensional vectors by vectors of smaller dimension
sIs there any (efficient) algorithm for the following problem:
Let $n = 128$ and $m = 64$ (in the end only $n > m$ matters) and $p_1, \ldots, p_t \in \{ -1,1 \} ^{128}$ be given ($t << 2^{...
- 397
0
votes
0
answers
276
views
Another matrix diagonalization problem
Given the matrices $X$ and $Y$ in $[0,1]^{n\times m}$, for $n > m > 3$, so that $X1_m=1_m$ and $Y1_m=1_m$, where $1_m$ denotes a $m$-length column vector of ones, find a matrix $Q$ in $R^{m\...
- 51
0
votes
0
answers
395
views
The ratio of two strictly increasing functions
Given:
\begin{equation}
f_1(a)=\sum_{i=1}^{k^*-1} \left(\begin{array}{c}
K \\\
i \\
\end{array} \right) \left(-1-\frac{1}{ar}\right)^i
\end{equation}
\begin{equation}
f_2(a)=\sum_{i=1}^{k^*-1} ...
0
votes
0
answers
109
views
Expansion (asymptotic) of scalar function of a square matrix , in terms of determinant of argument?
The title says it all. I have a scalar function (really, a determinant) of a square matrix argument. Can I find an (asymptotic) expansion of the function, in a series in the determinant of the ...
- 2,600