Given rank deficient matrix $A$, I want to randomly construct vectors $\vec{x}$ such that:
- $0 \le x_{j} \le 1$
- $0 \le b_{j} \le 1$ where $\vec{b} = A\vec{x}$
Matrix $A$ is about 10 x 15. I want to generate $10^{5}$ $\vec{x}$ as an initial guess in each iteration of a solver.
Below is my attempts.
Least square and rejection
- Generate $\vec{y}$ with entries between 0 and 1.
- Generate $\vec{b}$ with entries between 0 and 1.
- Minimize $(\vec{y} - \vec{x})^{2}$ subjected to constraint $A\vec{x} = \vec{b}$.
- Reject $\vec{x}$ that are out of bounds.
Problem: the rejection rate is very high. Very impractical even for a 10 x 15 matrix $A$.
Step 2 is equivalent to solving
$\begin{bmatrix} A & 0\\ I & A^{T} \end{bmatrix} \begin{bmatrix} \vec{x}\\ \vec{\lambda}\\ \end{bmatrix} = \begin{bmatrix} \vec{b}\\ \vec{y}\\ \end{bmatrix} $
Constrained Optimization
- Generate random $\vec{y}$ within bounds.
- Objective: $(\vec{x} - \vec{y})^2$.
- Constraint: $A\vec{x} = b$
- Bounds: between 0 and 1.
Problem: Optimization is too slow and often gives result out of bounds. Impractical.
Other ideas
- Null space
- Simplex, random planes, and projection
- Hit and run sampling