algorithm - Algorithmically correcting noisy distance measurements between data points on a number line -


i have application have data points x can mapped number line. however, don't know value on number line is. fortunately, don't need know exactly values are, need know distances between points (i.e. 0-point on number line arbitrary, , can reflected without affecting anything).

i have input set of transitive distance measurements d[i,j] between points. additionally, distance measurements oriented (i.e. d[i,j] = -d[j,i], d[i,j] > 0 indicating x[i] further right on number line x[j]).

first challenge: don't have of values of d, have control on values obtain.

ideally, wouldn't big of problem because choose pairs [i,j] d forms spanning tree (interpreting adjacency matrix of graph) , distance between x[i] , x[j] path length of walk between nodes i , j on tree. unfortunately...

second challenge: distance measurements noisy. in cases, noise small. however, in rare cases distance measurements wildly inaccurate.

so. problem. use multiple distance measurements between data points denoise these noisy distance measurements. here's wish list, of may turn out infeasible:

  • an algorithm maps points in x number line (with arbitrary 0-point) there single, unambiguous, transitive distance between x[i] , x[j], , clear 1 right of other.
  • the algorithm works graph d sparse, not tree. perhaps has property there @ least 2 paths between 2 nodes.
  • because multiple paths through d between 2 points represent different prospective distance measurements, use loss function minimizes difference of inter-data point distances in projection integrated value of distances implied d.
  • the algorithm uses loss function saturates high values. take care of case distances inaccurate, i'm worried make problem non-convex. l1 penalty might enough.

my first thought multidimensional scaling literature since it's concerned distance-preserving embeddings, don't think problem posed correctly. mds seems assume have single, unambiguous distance measurement between each point. that's not set up.

i'm interested in literature or algorithms people can point me to, whether aspect of problem, or similar problem, or same problem. thanks!

if can put l1 norm, think can minimize linear programming problem - tells convex problem, variety of other techniques, such simple hill-climbing , iteratively reweighted least squares, should converge global minimum.

arbitrarily set x0 = 0.

for each pair xi, xj have measurements add xi - xj - dij <= tij, dij - xi + xj <= tij, dij measurement

minimise sum_ij tij - minimised @ tij = |xi - xj - dij|, minimizes sum of l1 norms of errors.


Comments

Post a Comment

Popular posts from this blog

What is happening when Matlab is starting a "parallel pool"? -

running parallel cpu processes in matlab starts command parpool() according documentation , function: [creates] special job on pool of workers, , [connects] matlab client parallel pool. this function takes bit of time execute, on order of 30 seconds. in other multi-cpu paradigms openmp, parallel execution seems totally transparent -- i've never noticed behavior analogous matlab (granted i'm not experienced parallel programming). so, happening between time parpool() called , when finishes executing? takes long? parallel computing toolbox enables run matlab code in parallel using several different paradigms (e.g. jobs , tasks, parfor , spmd , parfeval , batch processing), , run either locally (parallelised across cores in local machine) or remotely (parallelised across machines in cluster - either 1 own, or 1 in cloud). in of these cases, code run on matlab workers , copies of matlab without interactive desktop. if you're intending run on remo...
Read more

angular - DownloadURL return null in below code -

when change file updated in firebase storage when try downloadurl show null. filechange(event: any) { const imagefolder: string = this.employee.id; const filelist: filelist = event.target.files; const file: file = filelist[0]; const storageref = firebase.storage().ref().child(`${imagefolder}/profile.jpg`).put(file); console.log(storageref.snapshot.downloadurl); } the put() asynchronous. if want url after file uploaded have this: firebase.storage().ref().child(`${imagefolder}/profile.jpg`).put(file).then((snapshot) => { storageref = snapshot.downloadurl: console.log(snapshot.downloadurl); });
Read more

php - Cannot override Laravel Spark authentication with own implementation -

during login process of laravel spark need request token of remote api. api stores exact same users , passwords laravel spark application. therefore need username , non hashed password of user during authentication process. i thought overriding authenticated method solution problem. in routes/web.php override post /login endpoint , pointing endpoint own logincontroller: <?php namespace app\http\controllers\auth; use illuminate\support\facades\log; use illuminate\http\request; use laravel\spark\http\controllers\auth\logincontroller sparklogincontroller; class logincontroller extends sparklogincontroller { /** * create new login controller instance. * * @return void */ public function __construct() { parent::__construct(); } /** * handle successful authentication attempt. * * @param request $request * @param \illuminate\contracts\auth\authenticatable $user * @return response */ public fu...
Read more