# Questions tagged [linear-algebra]

The tag has no usage guidance.

47 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
0answers
1k views

0answers
117 views

0answers
58 views

0answers
69 views

0answers
29 views

### Minimize number of math operation of a specific matrix vector multiplication?

Let's say we have a Matrix M and a column vector v like below multiply equals Assume we can only perform multiplication, addition and substraction operation. With normal approach we need 3 ...
0answers
32 views

### How is the modular multiplication matrix unitary in Shor's Algorithm?

I have been reading papers about the construction of this matrix in Shor's Algorithm all night. The behavior of the controlled modular multiplication matrix is described as C U_{a^{2}}(|c\rangle|y\...
0answers
61 views

### Confusion about the geometric interpretation of the simplex method for linear programming

In Section 7.6.2 of the textbook "Algorithms" by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani, the authors provide a geometric interpretation of the two main tasks of each iteration of ...
1answer
17 views

### Smallest Circuit for Square of Sparse Symmetric Matrix

I have an n by n symmetric matrix, and I would like to compute its square in as small a circuit complexity as possible. It's sparse: there are sqrt(n) nonzero entries in each row/column, so the input ...
0answers
32 views

### Check if no linear combination is within a hypercube

Shapes Let $C$ be the unit hypercube in $\mathbb{R}^{n}$. Let $\vec{o}$ be a point in $\mathbb{R}^{n}$. Let $B$ be a $n \times m$ matrix. The columns of $B$ are a set of linearly independent vectors ...
0answers
22 views

### Sparse feasible solution $|x|_0\le k$ for system of linear inequalities $A x \le b$

Suppose the set of linear inequalities $Ax\le b$, in which $A\in\mathbb{R}^{m\times n},x,b\in\mathbb{R}^n$ is given. Is it possible to determine in polynomial time with regard to $m$ and $n$ if there ...
0answers
23 views

### Need help implementing an algorithm to solve roots of a transcendental equation

I'm trying to implement this algorithm but I'm having problems reproducing the exemple that it gives a solution to. The general method that I tried is: Make a grid $\theta \in [0,2\pi)$, with say N=...
0answers
55 views

### Sparse Matrix inversion without actual inversion

I want to know what are the efficient way to invert a Sparse Matrix? Are there any algorithm,linear algebra or expansions that make this task easier with out actually inverting the matrix? Thank you ...
0answers
25 views

### Construct unitary $Q$ such that $span\{q_1,q_2\} = span\{v_1,v_2\}$ where $v_1,v_2 \in \mathbb{R}^n$ are given as input

Assume also that $v_1,v_2$ are linearly independent, and $q_i \in \mathbb{R}^n$ denotes the $i$-th column of $Q$. This is what I've got so far. First obtain unit vectors $w_1,w_2$ which are orthogonal ...
0answers
24 views

### Want to do 3D reconstruction via simple matching

I have 2 images, called left and right images. I have some matched points $[c_l,r_l]$ and $[c_r,r_r]$ in both of them (these points are in pixel coordinates). For a 3D point in the real world, they ...
0answers
33 views

### Scalability of factor-solve vs. pseudoinverse + product

I’ve always read advice and warnings about the poor scalability and time spent trying to invert a matrix and why it’s better to solve a system of equations whenever the inverted matrix will be used ...
0answers
26 views

### Testing whether a set of integers can be written as a combination of module basis elements

Input We are given a set of basis elements, $\ v_1$,$\ v_2$ ,...,$\ v_n$ of a $\mathbb Z^m$- module and a multiset of integers $\ B :=$ {$\ b_1, ..., b_m$} Desired Output Return true if there ...
0answers
189 views

### How to solve linear system with modulus operation?

I came across linear equation $G(x,y) = g_k(x,y) l_k(x,y)$ mod $(y^{2^{k}})$ while reading factoring algorithm see section 3 for bivariate polynomials. I need to find the $G(x,y)$ and $l_k(x,y)$. ...
0answers
76 views

### Relation between determinant and matrix multiplication

I remember reading somewhere that if matrix multiplication can be done in $O(n^\omega)$ time then determinants can be computed in $O(n^\omega)$ time. I am unable to find the reduction and would it be ...
0answers
140 views

### Comparison of matrix determinant in less than $O(n^2)$

I was reading this question and I think maybe somebody here could help. This is the idea: Given a matrix $M$ of integers, and a number $d$ is there a way to compare the determinant of $M$ and $d$ in ...
0answers
109 views

### Laplace's Approximation for graphical models

A question about Laplace's approximation: In Laplace's method, we need to find the mode of a function and take second order Taylor's expansion. The first order term will vanish (since the gradient is ...
0answers
34 views

### Is this problem in P: Finding a common key for a collection of systems of equations?

Let $B=\{b_1=g_1,\cdots,b_n=g_n\}$ be a set of binary variables $b_i$ and their corresponding values $g_i \in \{0,1\}$. Let $M=\{\sum_{e \in A}e \;:\; A \subset B\}$, i.e., $M$ is the set of all ...
0answers
53 views

### How to quickly solve a linear equation for 7000 times?

I need to solve a linear equation Ax=b for 7000 times (A is sparse and complex square matrix), and at each time only 4 elements (A(i,k), A(i,m), A(j,k) and A(j,m)) are changed while all other elements ...
0answers
32 views

### How to make sure matrix completion can generate a matrix with values in expected range?

I am doing a matrix completion project. Assume that I have an incomplete matrix like ...
0answers
27 views

### Equivalent Algorithm with Sharman Morrison inversion

I am trying to invert a matrix using Woodbury identity. The inversion using Cholesky decomposition has the following pseudo-code: For $t=1,2,...$ $(1)\;\; \text{Read}\;x_t\in\mathbb{R}^n$ ...
0answers
32 views

### Randomly choose matrices $A_{j}B = C_{j}$ with elements between 0 and 1

Problem I have $J$ matrices $C_{j}$, which are $K \times M$. Elements of each matrix $C_{j}$ are between 0 and 1. I want to randomly choose $J$ matrices $A_{j}$ and one matrix $B$ such that: ...
0answers
119 views

### Why solutions for Normal form Ordinary least squares and Linear Regression are different

I am trying to apply Linear Regression method for a dataset of 9 sample with around 50 features using python. I have tried different methodology for Linear Regression i.e Closed form OLS(Ordinary ...
0answers
355 views

### Most stable algorithm to solve a system of linear equations?

I am doing some image processing involving solving a system of linear equations. I am getting some errors and bits of the image looks corrupted. I would like to know what is the most stable way to ...