Questions tagged [linear-algebra]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
1answer
18 views

Avoiding underflow when identifying neighbours of a cell in a grid by using modulo

I'm going through a tutorial that is using the Game of Life as example code. It has a function in it that finds the neighbor of a given cell. It is explained quickly that "When applying a delta of -1, ...
0
votes
1answer
197 views

LP formulation and integer solution existance

I’m trying to prove that the following problem has an integer optimal solution. This will hold if the corresponding linear program would have totally unimodular constraint matrix. We have $m$ pieces ...
0
votes
1answer
239 views

maximizing inner product of vectors in an ellipsoid and a given vector

I have been wrestling with this for quite a long time but couldn't convince myself that the following is true: What I do understand: $\theta_a$ denotes the set of points that are within the ellipsoid....
0
votes
1answer
102 views

Using random projections for locally sensitive hashing

I recently came to see that this library sparselsh uses random projection to perform locally sensitive hashing of documents. The proof is such that based on cosine similarity to the vector. In other ...
0
votes
1answer
77 views

Projecting points on a Pareto-front onto a (hyper)plane?

I'm trying to implement the Biased Crowding Distance in NSGA-II as described in the paper Integrating User Preferences into Evolutionary Multi-Objective Optimization by Branke and Deb. Basically, ...
0
votes
1answer
584 views

Running time of sparse matrix multiplication

Given a sparse matrix $M \in \mathbb{R}^{n \times m}$ with $n \ll m$ and $\mathsf{nnz}$ being the number of non-zero-components. What is the running time of computing $M M^T$?
0
votes
1answer
38 views

Using Taylor series in 1D Grayscale Image

Could someone point me in the direction of how to solve this? I = [I1, . . . , In] is a 1D grayscale image and D = [D1, . . . , Dn] represents the second derivative of I. I am given the four pixel ...
0
votes
1answer
142 views

Algorithm for projection of polytope

Let a convex bounded polytope be given by an intersection of half planes: $Ax \leq b$. Let $z=Cx$ be a vector (in my case $z$ is 2-dimensional, while $x$ has a higher dimension). How can I compute $D$...
0
votes
1answer
40 views

What is the exact definition of a dictionary in the concept of linear algebra and computer science?

I am reading this paper for my master thesis and trying to understand every concept in it. The following sentence confuses me as to what is the exact definition of a dictionary in this concept except ...
0
votes
0answers
52 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 ...
0
votes
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 ...
0
votes
0answers
26 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$ ...
0
votes
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: ...
0
votes
1answer
48 views

Compute unknown matrices that minimize a sum

This problem is about working with smart-phone accelerometers. To calibrate accelerometer, I need to find three unknown matrices T, K and B that minimize this sum: $$\sum_{i=0}^N(|g|^2 - |TK(a_i + B)|...
0
votes
0answers
115 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 ...
0
votes
0answers
338 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 ...
0
votes
1answer
108 views

Solving a graph problem by Gaussian elimination

I have been given a graph with n nodes. Now, I have to color every node of this graph by k colors, number from 0 to k-1. Now, there is a rule. For a node $x$ with adjacent nodes $y_1 , y_2, y_3, y_4,....
-1
votes
1answer
62 views

A max-even subset problem

I want to know if there is any polynomial algorithm for the problem, or any NP-completeness result. Given a set $S$ and $m$ subsets $C_1, \dots, C_m$ of $S$, we want to find a non-empty set $X\...