Questions tagged [norms]
Norms as in the l_p norms, normed vector spaces, matrix norms and so on.
12
questions
2
votes
0
answers
78
views
Obtaining a lower bound of a matrix norm
I was wondering (on a setting where $\vec X_i \sim \mathcal{N}(\vec\mu, \mathbb{I})$ are $n$ random $d$-dimensional multivariate normal vectors with unknown mean $\vec\mu$) how I could obtain a lower ...
- 21
0
votes
0
answers
139
views
Convex mixed linear integer programming with real nuclear norm objective and linear integer objective
Khachiyan and Porkolab in 'Integer optimization on convex semialgebraic sets' gave an $O(ld^{ O(k^4)})$ algorithm to minimize a degree $d$ form with integer coefficients of binary length at most $l$ ...
- 12.8k
1
vote
0
answers
127
views
Minimize L2 norm by circular permutation
Imagine two lists $L$, $M$ of the same length $n$. How to find $j$ such that
$\sum_{i=1}^n(L[i]-M[i+j])^2$ is minimal, where the index $i+j$ is taken modulo $n$?
Of course one can take all the ...
- 11
11
votes
1
answer
313
views
Any evidence that Linial, Shraibman lower bound on quantum communication complexity is not tight?
As far as I know, the factorization norm lower bound given by Linial and Shraibman is essentially the only lower bound known for quantum communication complexity (or at least it subsumes all others). ...
- 493
0
votes
1
answer
102
views
Confusion with the proof of constraints for a particular adiabatic quantum evolution
[This might be related to one of my previous unanswered questions.]
This proof belongs to the paper, How to Make the Quantum Adiabatic Algorithm Fail by Edward Farhi, Jeffrey Goldstone, Sam Gutmann ...
- 653
7
votes
1
answer
1k
views
The computational complexity of spectral norm of a matrix
How hard is computing the spectral norm of a matrix? This paper says,
... it suffices to say that, except for few particular cases, the Matrix
Norm problem is NP-hard.
I expected that the ...
- 653
3
votes
1
answer
196
views
Why spectral norms are used for computing the complexity of adiabatic Hamiltonian?
In the context of adiabatic quantum computation the spectral norm was first used in the first adiabatic paper by Farhi et. al. when he demonstrated the relation of it to the conventional quantum ...
- 653
11
votes
0
answers
147
views
expansion with respect to p-norms for p other than 2
Suppose I have an $d$-regular expander graph with $n$ vertices, where the stochastic version of its adjacency matrix $A$ (with entries $1/d$ and zero) has second eigenvalue $\lambda$.
Let $x \in {\...
- 119
17
votes
0
answers
366
views
complexity of checking if a subspace is a Euclidean section of L1
If $X$ is a linear subspace of ${\mathbb R}^n$, $X$ is high-dimensional, and for every $x\in X$ we have
$(1-\epsilon) \sqrt n ||x||_2 \leq ||x||_1 \leq \sqrt n ||x||_2$
for some small $\epsilon >...
- 4,902
7
votes
1
answer
379
views
Stronger Lower Bounds on Nondeterministic Multiparty Communication
This is a continuation of my previous question on Lower bounds for Nondeterministic Multiparty Communication.
From the answer, the $\mu^\infty$ norm lower bounds nondeterministic multiparty ...
- 3,280
11
votes
1
answer
480
views
Lower bounds for Nondeterministic Multiparty Communication
This is a continuation of my previous question on communication lower bounds for partial boolean functions.
Can someone suggest any reference on lower bounds for nondeterministic multiparty ...
- 3,280
20
votes
2
answers
1k
views
$\ell_p$-norm preserving Turing machines
Reading some recent threads on quantum computing (here,here, and here), make me remember an interesting question about the power of some kind of $\ell_p$-norm preserving machine.
For people working ...
- 3,280