## Constraint propagation using Projection rule

I’ve found this example of constraint propagation using projection rule We have

C = { x1 ≠ x2, x1 ≥ x2 }  < C; x1 ∈ {1,2,3}, x2 ∈ {1,2,3} > 

They say that applying propagation rule, does not give any simplification.

I’m not sure why this is the case. Shouldn’t we get?

< C; x1 ∈ {2,3}, x2 ∈ {1,2} > 

Other steps in the example, make sense that to me, e.g.

< C; x1 ∈ {2}, x2 ∈ {1,2,3} > 

produces

< C; x1 ∈ {2}, x2 ∈ {1} > 
Posted on Categories proxies

## Triangle solutions by projection on plane!

I have a little question. how many solutions has a triangle by the projection on the plane? Like the Patenoth problem but in 3d space.

## How to use known Projection Matrices of cameras to generate new fundamental matrix located correctly in 3D space?

I have a few cameras which have been calibrated (using a checkerboard) so I know the fundamental matrix between an origin camera and each remaining camera

I wish to take pairs of camera with no fundamental matrix – but each has a projection matrix – and calculate the fundamental matrix with the view to reconstruct the stereo pair in 3D. To clarify – as all cameras have a projection matrix – I should be able to take any combination and generate a Fundamental matrix – so I can reconstruct and combine stereo pairs in 3D using as many pairs as possible

currently I use this formula: (decomposing Projection matrices from camera to get C)

but that didn’t quite work with stereo pairs that don’t include the origin. I noticed that to calculate the fundamental matrix that rotation was relative so I added the relative rotation formula when recalculating P from K/R/T (intrinsic camera params, Rotation matrix, Translation matrix) but now each reconstruction appears on the camera position (I think) instead of all stereo pairs being mapped into same space to give a dense reconstruction

Does anyone know what I am doing wrong? thanks for any help

Posted on Categories proxies

## Graph of function, continuous projection

$$X$$ and $$Y$$ are topological spaces. $$f:X\rightarrow Y$$ a map (we don’t suppose that $$f$$ is continuous). Consider $$A=\{(x,f(x))\in X\times Y| x\in X\}$$. is $$\pi: A\rightarrow X$$, $$(x,f(x))\mapsto x$$ a homeomorphism ? If not, is it enough to assume that $$A$$ is closed subspace in $$X\times Y$$ ? If $$X$$ and $$Y$$ are metrizable spaces, how to prove that $$\pi$$ is a homemorphism using sequential continuity ? Suppose that by miracle $$\pi$$ is homeomorphism but $$f$$ is not continuous, is it possible such phenomenon ?

## Projection of a polytope along 4 orthogonal axes

Consider the following problem:

Given an $$\mathcal{H}$$-polytope $$P$$ in $$\mathbb{R}^d$$ and $$4$$ orthogonal vectors $$v_1, …, v_4 \in \mathbb{R}^d$$, compute the projection of $$P$$ to the subspace generated by $$v_1, …, v_4$$ (and ouput it as an $$\mathcal{H}$$-polytope).

I know that the problem of computing projections along $$k$$ orthogonal vectors in NP-hard (if $$k$$ and $$d$$ are part of the input), as shown in this paper. But does it help if $$k$$ is a constant? Specifically, does it help if $$k \leq 4$$? Do we have a polynomial algorithm in this case?

## Estimating quality of projection

Suppose we are given a vector $$v$$ and vectors $$\mu_i$$:

$$v = \mu_1+\mu_2+…+\mu_m$$, where $$\mu_i \in R^n$$, all $$\mu_i$$ are of unit length.

Oracle will give me $$k$$ vectors $$\mu_{j_1}, \mu_{j_2},…\mu_{j_k}$$ from the original set such that when I project $$v$$ onto subspace spanned by these vectors the length of the projection is highest possible. In other words, from the set of all combinations of $$k$$ vectors from $$[\mu_1,…\mu_n]$$ the $$[\mu_{j_1}, \mu_{j_2},…\mu_{j_k}]$$ give highest length of projection. Lets denote by $$v_{\text{proj}}$$ projection of $$v$$ onto $$[\mu_{j_1}, \mu_{j_2},…\mu_{j_k}]$$

I want to estimate quality of projection before oracle gives me this $$k$$ vectors. I want to give upper bound on $$||v – v_{\text{proj}}||$$

As far as I understood it is very difficult to obtain these $$k$$ vectors by myself. However, I know that for any two vectors $$\mu_i, \mu_j$$, $$||\mu_i-\mu_j|| \leq \alpha$$, where $$\alpha$$ is a given positive number.

Small values of $$\alpha$$ will tell me that all $$\mu_i$$ are close to each other and heading towards same direction. I would suspect then that projection will be good, and its length will be close to the length of original vector. How can I use this to give an upper bound $$||v – v_{\text{proj}}||$$?

My attempts:

Without loss of generality lets assume that $$k$$ optimal vectors are first $$k$$ vectors in the list, i.e $$\mu_1,\mu_2,…\mu_k$$. Lets denote by $$P$$ projection operator on the space spanned by $$\mu_1,\mu_2,…\mu_k$$.

$$\|v – v_{\text{proj}}\| = \|v – P(v)\| = \|v – P(\mu_1+\mu_2+…+\mu_m)\| =$$

$$\|v – P(\mu_1) – P(\mu_2) – … – P(\mu_m)\| =$$

$$\| v – \mu_1 – \mu_2 – … – \mu_k – P(\mu_{k+1}) – P(\mu_{k+2}) – … – P(\mu_m)\| =$$

$$\|\mu_{k+1} – P(\mu_{k+1}) + \mu_{k+2} – P(\mu_{k+2}) + … + \mu_{m} – P(\mu_{m})\|$$

$$\|v – v_{\text{proj}}\| \leq \|\mu_{k+1} – P(\mu_{k+1})\| + \|\mu_{k+2} – P(\mu_{k+2}) + … + \|\mu_{m} – P(\mu_{m})\|$$

$$\|v – v_{\text{proj}}\| \leq (m-k)\alpha$$

So in order to make $$\|v – v_{\text{proj}}\| \leq \epsilon$$, we need $$k \geq \frac{m\alpha – \epsilon}{\alpha}$$

I am not satisfied with this result because $$k$$ grows linearly with $$m$$. I want it to grow much slower, something like $$\log(m)$$. My goal is to show that under some constraints on $$\mu_i$$, we need only approximately $$\log(m)$$ vectors to approximate $$v$$.

I think the bound can be improved substantially. First Cauchy inequality isn’t very tight and second, I used $$|\mu_{k+1} – P(\mu_{k+1})\| \leq \alpha$$ which is also very loose.

I am open for additional constraints on $$\mu_1,…\mu_m$$ to achieve logarithmic growth

Alex Ravsky on math.se has noted, that we also need a constraint on $$\alpha$$ in order to achieve logarithmic growth. Assume that $$k$$ $$\leq n$$, $$\mu_i$$ is th $$i$$-th standard ort of the space $$\mathbb{R}^n$$, and $$\alpha = \sqrt{2}$$. Then $$\|v – v_{\text{proj}}\| = \sqrt{m-k}$$

## Projection of an invariant almost complex structure to a non integrable one

My apology in advance if my question is obvious or elementary

We identify elements of $$S^3$$ with their quaternion representation $$x_1+x_2 i +x_3 j +x_4 k$$. We consider two independent vector fields $$S_1(a)=ja$$ and $$S_2(a)=ka$$ on $$S^3$$. On the other hand $$P: S^3\to S^2$$ is a $$S^1$$-principal bundle with the obvious action of $$S^1$$ on $$S^3$$. Then the span of $$S_1, S_2$$ is the standard horizontal space associated to the standard connection of the principal bundle $$S^3 \to S^2$$. Then each horizontal space has an almost complex structure $$J$$. This is the standard structure associated to $$S_1, S_2$$ coordinate.

Is this structure invariant under the action of $$S^1$$? If yes, we can define a unique almost complex structure on $$S^2$$ which is $$P$$ related to the structure on total space. Now is this structure on $$S^2$$ integrable?

As a similar question, is there an example of a principal bundle $$P\to X,$$ such that $$P$$ is a real manifold and $$X$$ is a complex manifold and a connection admit an invariant almost complex structure which project to a non integrable structure?

## Uniqueness of projection under spectral norm

I am considering $$\min_{M\in \mathcal{M}} \|X – M\|:=x \neq 0,$$ where $$X$$, $$M$$ are $$m\times n$$ matrices, $$\|\cdot\|$$ is spectral norm and $$\mathcal{M}$$ is a matrix subspace. I wonder to what extent the solutions are unique, i.e. what can we say about the set $$\mathcal{M}^* = \{M|\|X – M\|=x\}.$$ Currently, I only know it is a convex set. For $$M_1, M_2 \in \mathcal{M}^*$$, let $$M = p M_1 + (1-p) M_2$$, $$p \in (0,1)$$. For any vector $$v$$, using Cauchy’s inequality, we have $$v^T(X – M)^T(X – M)v \leq x^2,$$ thus $$M \in \mathcal{M}^*$$. Moreover, the equality holds only when $$(X – M_1)v = (X – M_2)v = u,~~~~s.t.~u^T u = x^2.$$ I wonder whether there are more properties I could say about this set, e.g. its dimension/the properties of the common eigenvectors/the condition under which the solution is unique.

## Projection on space of permutations of lower diagonal matrices

Let $$G$$ be the group of all $$n\times n$$ permutation matrices and let $$V$$ be the vector space of all $$n$$-dimensional lower diagonal matrices. Then I define the set $$X = \{P\cdot L\cdot P^T \mid \forall P\in G, L\in V\},$$ where “$$\cdot$$” is matrix multiplication. That is, $$X$$ is the set of all lower diagonal matrices with possible rows and colums that are permuted at the same time.

I am interested in the orthogonal projection of a general matrix $$M\in\mathbb{R}^{n\times n}$$ on the set $$X\subset \mathbb{R}^n$$. Does anyone know if there is a more efficient method to do it than projecting on each space $$V_P = \{P\cdot L\cdot P^T \mid \forall L\in V\}$$ for every individual $$P\in G$$ and then taking the shortest one?

Let $$\mathcal{H}$$ be a real Hilbert space. For given $$a \neq b \in \mathcal{H}$$, we denote the line segment by $$\left[ a , b \right] := \left\lbrace \left( 1 – t \right) a + t b \ \colon \ t \in \left[ 0 , 1 \right] \right\rbrace .$$ Consider a convex set $$C$$ and assume that we can compute its projection $$P_{C} \left( x \right)$$ for every $$x \in \mathcal{H}$$.
Can we deduce the projection formula for the set $$\left[ a , b \right] \cap C$$?
It is clear that $$P_{\left[ a , b \right]} \left( x \right) = x$$ for $$x \in \left[ a , b \right]$$. When $$x \notin \left[ a , b \right]$$, we can compute its projection onto $$\left[ a , b \right]$$ notice that \begin{align} \left\lVert x – a \right\rVert & \leq \left\lVert x – y \right\rVert + \left\lVert y – a \right\rVert , \qquad \forall y \in \left[ a , b \right] , \ \left\lVert x – b \right\rVert & \leq \left\lVert x – y \right\rVert + \left\lVert y – b \right\rVert , \qquad \forall y \in \left[ a , b \right] . \end{align} Taking the infimum on bothsides we can also get an explicit formula for the projection, in particular $$P_{\left[ a , b \right]} \left( x \right) = \begin{cases} x & \textrm{ if } x \in \left[ a , b \right] , \ a & \textrm{ if } x \notin \left[ a , b \right] \textrm{ and } \left\lVert x – a \right\rVert \leq \left\lVert x – b \right\rVert , \ b & \textrm{ if } x \notin \left[ a , b \right] \textrm{ and } \left\lVert x – a \right\rVert \geq \left\lVert x – b \right\rVert . \end{cases}$$