Questions tagged [least-squares]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
0answers
68 views

Stable Method of orthogonal projection onto a subspace with the help of Moore-Penrose inverse,

Projection of a vector $v$ onto the column space of a matrix $A$ is given by $AA^\dagger v$. From the definition of Moore-Penrose Inverse we know that $AA^\dagger v = (A^T)^\dagger A^T v $. Below is ...
3
votes
0answers
88 views

Backward stable algorithm to get orthogonal projection onto the column space of a matrix

I have to find the orthogonal projection of a vector $b$ onto the matrix $A$ of size $m \times n$. In my application, I don't have the luxury of calculating the QR factorization. All I have are ...
0
votes
1answer
202 views

Linear Least-Squares Point-to-Plane ICP degenerative case

I'm trying to implement Linear Least-Squares Optimization for Point-to-Plane ICP Surface Registration Paper describes linear approximation for point to plane distance for rigid ICP. This approach is ...
2
votes
1answer
150 views

Solving sparse least squares system with limited memory

This was a question on a past final that we can't figure out. Take the least squares system $$\min_x ||Ax-b||_2\, ,$$ where $A\in\mathbb{R}^{mxn}$, $m<n$, and A is full rank. A has $\mathcal{O}(n)...
0
votes
2answers
57 views

Finding parameters numerically

I suspect that a function $f(x,y)$ is of the form $f(x,y)=a(bx+c)^{dy+e}$. I have access to several values of $f(x,y)$. How do I proceed numerically to find the parameters $\{a,b,c,d,e\}$? By ...
1
vote
1answer
71 views

Solving for $C$ in $Q = YCZ$ using least squares in Matlab

I am trying to solve for the matrix $C$ in $Q = YCZ$ in matlab. I have preliminary results but they don't seem realistic. Here, $Q$ is $n \times m-1$, $Y$ is $n \times p$, $C$ is $p \times m$ and $Z$ ...
7
votes
2answers
7k views

Least Squares and Fourier Series

I have a little bit of problem figuring out the relation between Fourier series and Least Squares. As far as I understand, LS is a way of minimizing the quadratic error between a measured value $y_i$ ...
2
votes
1answer
88 views

Description of algorithm for small scale linear least squares with box constraints

I have small scale dense least squares problem with box constraints $$\mbox{argmin}||Ax - b||^2 \quad $$ $$\mbox{subject to} \quad l_i \leq x_i \leq u_i,$$ Number of variables is about 10-50, ...
3
votes
1answer
75 views

Solving multiple least-square problems with the same constraints

The following least-square problem can be solved efficiently (e.g. using matlab's lsqlin): $$\vec{x}^*=\arg\min_\vec{x} ||C\vec{x}-\vec{t}||^2\,\ s.t.\ Ax \le \vec{b}$$ where the parameters of the ...
1
vote
2answers
43 views

Optimisation of purely integer quantity with bound-constraints for a 1D expensive function whose analytical form is not available

I have a computationally expensive objective function, whose analytical form is not available. The only input argument to the objective function is an integer variable. The goal is to compute the ...
1
vote
1answer
129 views

Least square with rectangular function

I have the function $c(t) = A \cdot \cos \left(\dfrac{2\pi}{\tau} \cdot t + \phi \right) $ which is used to define $ T(t) = \begin{cases} M + c(t), & c(t) > 0 \\ M, &c(t) \leq 0. \end{...
1
vote
2answers
221 views

Efficient methods to solve large dense singular least square problem (linear system)

I am trying to solve a singular linear least square problem: $$minimize: \phantom{2} ||Ax-b||^2 \\ subject \phantom{2} to: \phantom{2} x \ge 0$$ Here $ A \in R^{n \times m} $, and $ n\lt m$. here m ...
5
votes
3answers
1k views

Least Squares: Numerically, is solving normal equations okay for nice matrices?

I have to solve a least squares problem: $$ x=\arg \min\|Ax-b\| $$ where $A$ is a $m\times n$ matrix, $m>n$, and $b\in\mathbb{R}^m$. I always thought that doing this via QR factorization is ...
0
votes
1answer
281 views

How to code gradient descent-based Tikhonov denoising that exactly matches LSQ Tikhonov denoise?

(Note: Corrected code is posted below the original code.) For an exercise in optimization, I am interested in coding a simple example from scratch: a Tikhonov denoising routine using gradient descent,...
2
votes
0answers
42 views

$(max(0, f(x)))^2$ or $(max(0, exp(f(x))))^2$ for soft constraints with Gauss-Newton

I need some kind of inequality constraint in my optimization problems (rude version of SVM for example or skeleton based mesh fitting). However hard constraints is not suitable for me because ...
2
votes
0answers
27 views

Choosing suitable polynomial degree based on information in advection stencil

I'm working on a finite volume advection scheme for unstructured meshes which uses a multidimensional polynomial weighted least squares fit for interpolating from cell centres onto faces. In 2D, the ...
5
votes
1answer
118 views

Large scale triangular least squares

I have to solve the following least squares problem: \begin{equation} \| \left[ \begin{smallmatrix} \mathbf{L} \\ \mathbf{I} \end{smallmatrix} \right]\mathbf{x} - \mathbf{b} \|_2^2 \end{equation} ...
2
votes
1answer
106 views

Parameter reduction algorithm for least square model

Question I am performing least squares fitting using an objective function of the form $f(\mathbf{x})$ where $\mathbf{x}$ is a vector of parameters containing around 20 elements. The model function ...
4
votes
1answer
184 views

Best solver/preconditioner for least-squares finite element method

I have seen a lot of literature, lecture videos, etc. on solvers/preconditioners for non-symmetric and/or indefinite systems. However, now I want to solve the mixed poisson/Darcy equation using the ...
1
vote
1answer
11k views

MATLAB Code Evaluation for Least Squares Regression (LSR) [closed]

Below is my own approach to implement the Least Squares Regression algorithm in MATLAB. Could you please take a look and tell me if it makes sense; if it does exactly what is supposed to do? EDIT: ...
5
votes
2answers
2k views

How to determine whether two cylinders intersect or not?

Considering any two cylinders, defined as: the center of their bottoms $A_i$, the radius of their bottom $R_i$, the unit vector $W_i$ of their axis direction, and the length $L_i$ of the cylinders, ...
2
votes
1answer
291 views

Minimizing Cost Functions using Iterative Least Squares

I am currently trying to use iterative least squares to solve a system, $y = Hx + v$ where $y$ is a vector of observations, $H$ is the design matrix, and $v$ is the observation error. From my ...
2
votes
0answers
114 views

Calculating theoretical order of accuracy of least squares fit advection scheme

I'm familiar with finding the order of accuracy using von Neumann analysis for finite difference schemes formulated using Taylor series expansions. But is there a similar technique for finding the ...
2
votes
0answers
69 views

Fortran solver for the Sparse LSE problem

I was wondering if there is a Fortran library that contains a solver for the Sparse LSE(linear equality-constrained least squares) problem $$ min_{x}\|Cx-d\|^2 \text{ subject to } Ax=b $$ where $A$ ...
1
vote
1answer
345 views

Least Square fit with Double Zernike Polynomials

I need to describe the optical aberrations of my set-up with Zernike polynomials. To do this, I want to fit the first 15 polynomials in the following way on my data: $$\chi^2 = \sum_k\left(\beta_k^x -...
2
votes
1answer
211 views

Projecting onto convex shapes - best fit convex polygon

I am interested in studying a problem of the form $\min F(\Omega)$ where $\Omega$ varies in the class of convex, open sets in the plane. An idea is to deform $\Omega$ at each step using a steepest ...
1
vote
0answers
59 views

linear solution of curve fitting on multiple linear functions differing by a multiplier

I am facing the following problem. I know nonlinear least squares can provide a solution but I am wondering if a linear way to solve this data fitting problem may exists. This is my input dataset: I'...
1
vote
3answers
335 views

rank-deficient NNLS

I want to find the minimum-norm solution to a rank-deficient least-squares problem, subject to positivity constraints, e.g. $$\min_x\ \|x\|^2 \quad s.t.\quad Ax = b,\ x \geq 0$$ where $A$ is large, ...
3
votes
0answers
1k views

Polynomial Fitting with Least Squares using Numpy and Scipy

I am trying to fit data to a polynomial using Python - Numpy. The points, with lines sketched above them are as in the picture. I am trying to fit those points to a polynomial of 4. or 5. degree. ...
3
votes
1answer
996 views

solving a linearly-constrained sparse linear least-squares problem

[ question reposted from https://math.stackexchange.com/questions/786612/solving-a-linearly-constrained-sparse-linear-least-squares-problem ] Given the system of equations $Ax=b$, subject to $Cx\le ...
1
vote
1answer
89 views

Least squares fitting

I have the following equation I came across which was solved using least squares $x = \sum_{n=1}^{N} A_{n} y_{n}$ Where $x$ is a $m \times p$ matrix and $y$ would be of size $m \times p$ as well ,...
1
vote
1answer
72 views

Least Angle when $\textbf{A}^T\textbf{A}$ is singular

I'm teaching myself this regression stuff, so forgive me if this is a basic question. I can't seem to find a discussion of my particular problem. So I'm least-squares-ing this overdetermined system $\...
4
votes
1answer
85 views

Does the covariance matrix in Least Squares depend upon the input data?

I had always assumed that the covariance matrix depends upon the amount and quality of your input data, but I am finding out that this is not the case. Is this true? We want to fit $f(t) = \Sigma_{i=...
2
votes
1answer
993 views

Solve Regularized Least Squares problems using Matlab optimization toolbox

I am trying to solve a least squares problem where the objective function has a least squares term along with L1 and L2 norm regularization. I am unable to find which matlab function provides the ...
3
votes
1answer
269 views

Large-scale box-constrained linear least-squares

I need to solve $$\mbox{min}||Ax - b||_2^2 \quad \mbox{s.t.} \quad l \leq x \leq u,$$ where $A \in R^{m \times n}$, $m \ll n$, $n \approx 10^4-10^5$. BVLS [1] based on active-set method works fine ...
1
vote
1answer
1k views

How can I reuse the SVD of matrix A to solve LS problems for both A and its transpose via Eigen C++?

If $A\in R^{m\times n}, b\in R^m, c\in R^n$, if I need to solve the least square problems via SVD of $A$ and $A^T$, i.e. I need to solve the least square solutions to following linear systems via ...
2
votes
2answers
1k views

Solving non-negative least squares in Matlab (by analogy with least squares)

There is a least-squares problem. It can be solved using backslash in Matlab. If Ax = b, then x = A \ b. Let's assume that I ...
0
votes
1answer
197 views

How to recover the 3x4 pinhole camera from 9 parameters

I downloaded the bundle adjustment data from this link: original data for bundle adjustment which is the supporting data for a paper titled: Bundle Adjustment in the Large I want to use the data ...
4
votes
1answer
160 views

Factorization for reweighted least squares

I am solving a problem using an iteratively-reweighted least squares method: http://en.wikipedia.org/wiki/Iteratively_reweighted_least_squares Essentially this requires solving a number of least-...
3
votes
1answer
487 views

indirect method for least-squares with inequality constraints

I aim to find $x \in \mathbb{R}^n$ that $\min_x |D \cdot F \cdot x|^2$ subject to $x_i = X_i$ and $x_j \geq X_j$ , $i \in I, j \in J$ and I and J partition ${1\cdots N}$ into two sets. it is ...
6
votes
1answer
251 views

Proving convergence of adaptive finite elements - min res FEM?

There's a body of work out there dealing with the discrete convergence of adaptive finite element methods using error estimators. Most deal with proving the property $\|u-u_{k+1}\|_U \leq (1-\alpha) \...
1
vote
1answer
203 views

FETI-DP or BDDC with least squares FEM?

Have FETI-DP or BDDC methods been applied to alternative FEM discretizations - for example, least squares finite elements? My Google searching doesn't seem to yield many results, so I'm wondering if ...
5
votes
0answers
1k views

Using MINPACK for curve fitting: implementation?

I need to implement a non-linear fitting algorithm in Fortran and chose to use MINPACK's flavor of the Levenberg-Marquardt algorithm as a basis for the least-squares stuff. However, I seem to ...
0
votes
1answer
402 views

SVD regularization - ray 2D tomography

Sunny day today, isn't it? Please, I need help with my problem. I have written a program to do 2D ray tomography, according to this paper. For the result, I use formula (4.15) from the paper. Now I ...
6
votes
3answers
472 views

How to solve a small least-squares problem

This question is not very deep. Suppose I have a small rectangular matrix $A$, with number of rows and columns between $50$-$100$, respectively. Given a right-hand side $b$, I want to solve the least-...
8
votes
1answer
6k views

Fitting one set of points to another by a rigid motion

I'm not really sure how to explain this problem clearly, so please bear with me. I have a basis of 3 orthonormal unit vectors and a position, a standard 4x4 transform matrix in computer graphics. ...
6
votes
4answers
2k views

parameters estimation

I have to estimate a parameter (K), but I don't know how I can do it. I think by a regression model (minimum least square?), but I'm not sure. The system is: ...
4
votes
2answers
580 views

Complex least-squares problem

Having a matrix $\mathbf{A} \in \mathcal{C}^{m\times n}$ I solve following least-squares problem $$Re(\mathbf{A}^H \mathbf{A})x=Re(\mathbf{A}^H\mathbf{b}).$$ If the matrix $\mathbf{A}$ was a real ...
0
votes
0answers
224 views

computation complexity of OLS in estimating a VAR model

Could someone tell me the computation cost of using Ordinary least squares in estimating a Vector autoregression model? I am thinking the cost is O(n) where n is the number of the training instance. ...
3
votes
1answer
199 views

How do you formulate the linear least-squares method for radiometric calibration?

In Debevec and Malik (mentioned similarly in Forsyth and Ponce's Computer Vision: A Modern Approach) they highlight a method of solving the camera response function using linear least-squares. We ...